LeetCode： Binary Search

Question

Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -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

Binary Search (二分搜索法) 是搜尋演算法中的基本款。 大概的想法是取 nums 集合長度的ㄧ半為中間值 nums(mid)，接著再以這個中間值與其他元素值來比對。 如果假設的中間值大於目標值 target，則縮小右半部的搜尋範圍 max = mid - 1，反之也是如此。 這樣做的好處是每次比對後都可以過濾掉一半的元素，以縮小範圍的做法來加快搜尋的速度。 如果整個 while 迴圈都跑完也沒有比對成功，就代表沒有目標值的元素，回傳 -1。

def search(nums, target)
  min = 0
  max = nums.length - 1
  while min <= max
    mid = (min + max) / 2
    if nums[mid] == target
        return mid
    elsif nums[mid] > target
        max = mid - 1
    else
        min = mid + 1
    end
  end
  return -1
end

Explanation #1

以 Example 1 來說

Input: nums = [-1,0,3,5,9,12], target = 9
第一圈
min = 0
max = 5
while 0 <= 5
  mid = 2
  if (muns(2)=>3) == 9
    # won't enter here
  elsif (muns(2)=>3) > 9
    # won't enter here
  else (muns(2)=>3) < 9
    min = (mid=>2) + 1
  end
end

第二圈
min = 3
max = 5
while 3 <= 5
  mid = 4
  if (nums[4]=>9) == 9
    return 4
  elsif
    # won't enter here
  else
    # won't enter here
  end
end