LeetCode Js-704. Binary Search

    AllenLi
    LeetCode Js-Array

    Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

    給予一個有升冪排序(小到大)的整數陣列 nums 與一個整數目標。
編寫一個函式在 nums 中尋找 target。
如果目標存在則返回陣列位置，否則返回 -1。

    Example 1:

    Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

    Example 2:

    Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

    Solution:
    1. 設定 left 為 0， right 為 nums 的長度 – 1。
    2. while 迴圈處理當 left <= right 時，持續更新搜尋範圍。 

    left:  v –>
nums: [口,口,口,口,口]
right:         <--v

    Code.1:

    var search = function(nums, target) {
  let left = 0, right = nums.length - 1

  while (left <= right) {
    let middle = Math.floor((left + right) / 2)

    if (nums[middle] === target) {
      return middle
    } else if (nums[middle] > target) {
      right = middle - 1      
    } else if (nums[middle] < target) {
      left = middle + 1
    }
  }
  return -1
}

Code.2:

    var search = function(nums, target) {
    return nums.indexOf(target)
};

    

    FlowChart:
    
Example 1
    

    Input: nums = [-1,0,3,5,9,12], target = 9
let left = 0, right = nums.length - 1 //5

step.1 while(left <= right)
middle = Math.floor((left + right) / 2) => (0 + 5) / 2 = 2(2.5)
nums[2] < target //3 < 9
left = middle + 1 //2 + 1 = 3

step.2 while(left <= right)
middle = Math.floor((left + right) / 2) => (3 + 5) / 2 = 4
nums[4] === target //9 = 9
return middle // 4

    

    Example 2
    

    Input: nums = [-1,0,3,5,9,12], target = 2
let left = 0, right = nums.length - 1 //5

step.1 while(left <= right)
middle = Math.floor((left + right) / 2) => (0 + 5) / 2 = 2(2.5)
nums[2] < target //3 > 2
right = middle - 1 //5 -1 = 4

step.2 while(left <= right)
middle = Math.floor((left + right) / 2) => (0 + 4) / 2 = 2
nums[4] > target //3 > 2
right = middle - 1 //4 - 1 = 3

step.3 while(left <= right)
middle = Math.floor((left + right) / 2) => (0 + 3) / 2 = 1(1.5)
nums[1] < target //0 < 2
left = middle + 1 //1 + 1 = 2

step.4 while(left <= right)
middle = Math.floor((left + right) / 2) => (2 + 3) / 2 = 2(2.5)
nums[2] > target //3 > 2
right = middle - 1 //2 - 1 = 1

step.5 while(left > right) //2 > 1
return -1   

    

    IndexOf()
    

    indexOf()：回傳第一個指定元素在陣列中的位置，若不存在則返回-1。

const beasts = ['ant', 'bison', 'camel', 'duck', 'bison'];

console.log(beasts.indexOf('bison'));
// expected output: 1

// start from index 2
console.log(beasts.indexOf('bison', 2));
// expected output: 4

console.log(beasts.indexOf('giraffe'));
// expected output: -1

    

    Math.floor()
    

    Math.floor()：回傳小於等於該數字的最大整數。

console.log(Math.floor(5.95));
// expected output: 5

console.log(Math.floor(5.05));
// expected output: 5

    

    ex.此題與「LeetCode Js-35. Search Insert Position」類似觀念。

    Related Posts