Binary Search

Given a sorted array of distinct integers and a target, return the index of the target, or -1 if it's not present.

Example

Input: nums = -1 0 3 5 9 12, target = 9 Output: 4

Approach

Classic binary search: maintain low/high bounds, check the midpoint, and narrow to the half that could still contain the target.

Walkthrough

python

1def binary_search(nums, target):
2    low, high = 0, len(nums) - 1
3    while low <= high:
4        mid = (low + high) // 2
5        if nums[mid] == target:
6            return mid
7        elif nums[mid] < target:
8            low = mid + 1
9        else:
10            high = mid - 1
11    return -1

Step 1 / 2

First check: mid = (0+5)//2 = 2, nums[2] = 3. 3 < 9, so search the right half — low becomes 3.

Input format

Line 1: the array, space-separated Line 2: target