Binary Search

Problem

https://leetcode.com/problems/binary-search/

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.

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

Constraints:

• 1 <= nums.length <= 10:sup:`4`

• -10:sup:`4`< nums[i], target < 10:sup:`4`

• All the integers in nums are unique.

• nums is sorted in ascending order.

Pattern

Array, Binary Search

Approaches

Binary Search

Explanation

We can use binary search to find an element in a sorted array. The idea behind binary search is that because the array is sorted, we can eliminate half of the elements in each iteration by comparing target with the midpoint of the array, repeating until we find target or the search space is empty.

We use left and right pointers to track the current search space. Each iteration, we calculate the midpoint mid and compare nums[mid] with target. If they are equal, we return mid. Otherwise, we adjust the search space by moving the left or right pointer to mid + 1 or mid - 1 respectively.

Code

def search(nums: list[int], target: int) -> int:
    """Search for ``target`` in sorted ``nums`` using binary search."""
    left = 0
    right = len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Test

>>> from binary_search__binary_search import search
>>> search([-1, 0, 3, 5, 9, 12], 9)
4
>>> search([-1, 0, 3, 5, 9, 12], 2)
-1

Complexity

\(n\) is the length of the input array.

Measure	Complexity	Notes
Time	\(O(\log n)\)	search space halves each iteration
Auxiliary Space	\(O(1)\)	only two pointers

binary_search__binary_search.search(nums: list[int], target: int) → int

Search for target in sorted nums using binary search.