Binary Search

TIP

Inspired by https://labuladong.gitbook.io/algo-en/iii.-algorithmic-thinking/detailedbinarysearch

Iterative Binary Search

This is the common binary search where a sorted array nums is given and we are tasked to find target in that array.
Returns the index of the target if it exist in the array, else returns -1.

Time Complexity: O(logn)
Space Complexity: O(1)
Time complexity is O(logn) as the search range is halved every iteration until target is found. The iterative approach will give a O(1) space complexity.

Binary Search

Recurrerence Relation: T(N) = T(N/2) + O(1)

def binarySearch(nums, target):
    left, right = 0, len(nums)-1
    while left <= right: # Search interval = [left, right]
        mid = (left + right) // 2
        if nums[mid] == target: # target found! Return index
            return mid
        elif nums[mid] < target: # recurse right -> [mid+1, right]
            left = mid + 1
        elif nums[mid] > target: # recurse left -> [left, mid-1]
            right = mid - 1
    # Target not found -> return -1
    return -1

Search Interval

while left <= right:...

This gives us a closed interval of [left, right] to search from where both the left and right boundaries are included. This also means that our initial right boundary would have to be len(arr) - 1.

Case 1: nums[mid] < target
Target lies on the right side of mid and we would have to set our search interval to [mid + 1, right]. To do so, we have to set our left interval to mid + 1.

Case 2: nums[mid] > target
Target lies on the left side of mid and we would have to set our search interval to [left, mid - 1]. To do so, we have to set our right interval to mid - 1.

The terminating condition for this while loop would be when left > right.

Find Left Border

def bsLeftBorder(nums, target):
    if not nums:
        return -1
    left = 0
    right = len(nums)
    while left < right: # [left, right)
        mid = (left + right) // 2
        if nums[mid] == target: # [left, mid)
            right = mid
        elif nums[mid] < target: # [mid + 1, right)
            left = mid + 1
        elif nums[mid] > target: # [left, mid)
            right = mid

    print(left) # left => number of elements smaller than target

    # If we want to return -1 when target not found
    if left >= len(nums) or nums[left] != target:
        return -1
    return left # returns index of left border

Find Right Border

def bsRightBorder(nums, target):
    if not nums:
        return -1
    left = 0
    right = len(nums)
    while left < right: # [left, right), terminating condition: left == right
        mid = (left + right) // 2
        if nums[mid] == target: # [mid + 1, right)
            left = mid + 1
        elif nums[mid] < target: # [mid + 1, right)
            left = mid + 1
        elif nums[mid] > target: # [left, mid)
            right = mid
    # nums[left-1] may be the target
    if left == 0 or nums[left-1] != target:
        return -1
    return left - 1

Search In Rotated Sorted Array

good question

This leetcode question will test your true understanding of binary search.

Solution:

def search(self, nums):
    l = 0
    r = len(nums)
    while l < r: # [l, r), terminating condition: l == r
        mid = (l + r) // 2
        if nums[mid] == target:
            return mid
        # target and mid on same side
        if (nums[mid] < nums[0]) == (target < nums[0]):
            # perform binary search
            if nums[mid] < target: # [mid + 1, r)
                l = mid + 1
            elif nums[mid] > target: # [l, mid)
                r = mid
        # target on right side, search right
        elif (target < nums[0]): # [mid + 1, r)
            l = mid + 1
        # target on left side, search left
        else: # [l, mid)
            r = mid
    # Not found
    return -1