Binary Search

Problem Statement

You are given an array of distinct integers nums, sorted in ascending order, and an integer target.

Implement a function to search for target within nums. If it exists, then return its index, otherwise, return -1.

Your solution must run in O(log n) time.

Example 1:

Input: nums = [-1,0,2,4,6,8], target = 4


Output: 3

Example 2:

Input: nums = [-1,0,2,4,6,8], target = 3


Output: -1

Constraints:

  • 1 <= nums.length <= 10000.
  • -10000 < nums[i], target < 10000

You should aim for a solution with O(log n) time and O(1) space, where n is the size of the input array.

You should aim for a solution with O(log n) time and O(1) space, where n is the size of the input array.

Hint 1

Can you find an algorithm that is useful when the array is sorted? Maybe other than linear search.

Hint 2

The problem name is the name of the algorithm that we can use. We need to find a target value and if it does not exist in the array return -1. We have l and r as the boundaries of the segment of the array in which we are searching. Try building conditions to eliminate half of the search segment at each step. Maybe the sorted nature of the array can be helpful.

Hint 3

We compare the target value with the mid of the segment. For example, consider the array [1, 2, 3, 4, 5] and target = 4. The mid value is 3, thus, on the next iteration we search to the right of mid. The remaining segment is [4,5]. Why?

Hint 4

Because the array is sorted, all elements to the left of mid (including 3) are guaranteed to be smaller than the target. Therefore, we can safely eliminate that half of the array from consideration, narrowing the search to the right half and repeat this search until we find the target.

Solution

def binary_search_recursive(l: int, r: int, nums: list[int], target: int) -> int:
    if l > r:
        return -1
    m = l + (r - l) // 2


    if nums[m] == target:
        return m
    if nums[m] < target:
        return binary_search_recursive(m + 1, r, nums, target)
    return binary_search_recursive(l, m - 1, nums, target)




def search(nums: list[int], target: int) -> int:
    return binary_search_recursive(0, len(nums) - 1, nums, target)

Time complexity: O(log n) Space complexity: O(log n)

def search(nums: list[int], target: int) -> int:
    l, r = 0, len(nums) - 1


    while l <= r:
        # (l + r) // 2 can lead to overflow
        m = l + ((r - l) // 2)


        if nums[m] > target:
            r = m - 1
        elif nums[m] < target:
            l = m + 1
        else:
            return m
    return -1

Time complexity: O(log n) Space complexity: O(1)

Upper Bound

def search(nums: list[int], target: int) -> int:
    l, r = 0, len(nums)


    while l < r:
        m = l + ((r - l) // 2)
        if nums[m] > target:
            r = m
        elif nums[m] <= target:
            l = m + 1
    return l - 1 if (l and nums[l - 1] == target) else -1

Time complexity: O(log n) Space complexity: O(1)

Lower Bound

def search(nums: list[int], target: int) -> int:
    l, r = 0, len(nums)


    while l < r:
        m = l + ((r - l) // 2)
        if nums[m] >= target:
            r = m
        elif nums[m] < target:
            l = m + 1
    return l if (l < len(nums) and nums[l] == target) else -1

Time complexity: O(log n) Space complexity: O(1)

Built-In Function

import bisect


def search(nums: list[int], target: int) -> int:
    index = bisect.bisect_left(nums, target)
    return index if index < len(nums) and nums[index] == target else -1

Time complexity: O(log n) Space complexity: O(1)