704. Binary Search

Description

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.

You must write an algorithm with O(log n) runtime complexity.

Solution

Prerequisites for using binary search:

  • Ordered list
  • All elements are unique (if not, the value returns probably is not unique)

For binary search method, one important thing is to clearly define interval’s close and open situation. Usually we have two kinds of intervals:

  • Left close and right close [left, right]
  • Left close and right open [left, right)

For left close and right close [left, right]

Two points:

  • while (left <= right) should use <=, because it’s meaningful ween left == right since we use [left, right]
  • if (nums[middle] > target) right we need to let nums[middle] = - 1，because we are sure nums[middle] is not our target，so the ending condition is when we come across element with index is -1
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        
        while left <= right:
            middle = (left + right) // 2  #Floor Division

            if nums[middle] < target:
                left = middle + 1
            elif nums[middle] > target:
                right = middle - 1
            else:
                return middle
        return -1

For left close and right open [left, right)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left,right  =0, len(nums)
        while left < right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid+1
            elif nums[mid] > target:
                right = mid
            else:
                return mid
        return -1