704. Binary Search

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

Note:

You may assume that all elements in nums are unique.
n will be in the range [1, 10000].
The value of each element in nums will be in the range [-9999, 9999].

Source

Code

In [1]:

def binary_search(nums, target):
    """Iterative implementation of binary search"""
    left = 0
    right = len(nums)-1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            left = mid+1
        if target < nums[mid]:
            right = mid-1
    return -1

In [2]:

def binary_search(nums, target):
    """Alternative version of above solution"""
    left = 0
    right = len(nums)              # vs. len(nums)-1
    while left < right:            # vs. <=
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            left = mid+1
        if target < nums[mid]:
            right = mid            # vs. mid-1
    return -1

Check

In [3]:

nums = [-1,0,3,5,9,12]
target = 9
binary_search(nums, target)

Out[3]:

In [4]:

nums = [-1,0,3,5,9,12]
target = 2
binary_search(nums, target)

Out[4]:

-1

Follow up:

Solve it both iteratively and recursively. Solve it using built-in methods too.

In [5]:

def binary_search(nums, target):
    """Recursive implementation of binary search"""
    def helper(left, right):
        if right < left:  # base case: target not present
            return -1

        nonlocal nums, target
        mid = left + (right-left)//2

        if nums[mid] == target:  # base case: target at middle index
            return mid
        if target > nums[mid]:
            return helper(mid+1, right)
        else:
            return helper(left, mid-1)



    return helper(0, len(nums)-1)

In [6]:

def binary_search(nums, target):
    """Using Built-in method index()"""
    try:
        return nums.index(target)
    except ValueError:  # index() returns an error if target is not in nums
        return -1

In [7]:

from bisect import bisect_left

def binary_search(nums, target):
    """Using Built-in method bisect_left()"""
    i = bisect_left(nums, target) 
    return i if i != len(nums) and nums[i] == target else -1  