Coding Interview PatternsBinary Search
EasyModified Binary Search

Binary Search

Explanation & Solution

Practice Problem

Description

Given a sorted array of integers nums in ascending order and an integer target, write a function to search target in nums. If target exists, return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Input:nums = [-1, 0, 3, 5, 9, 12], target = 9
0
-1
1
0
2
3
3
5
4
9
5
12

Output: 4

Explanation: 9 exists in nums and its index is 4.

Constraints

  • 1 <= nums.length <= 10^4
  • -10^4 < nums[i], target < 10^4
  • All integers in nums are unique
  • nums is sorted in ascending order

Approach

Modified Binary Search pattern

1. Initialize Two Pointers

  • Set left = 0 and right = nums.length - 1 to cover the entire array.

2. Loop While Search Space Is Valid

  • Continue while left <= right.
  • Compute mid = (left + right) >> 1 (integer division by 2).

3. Compare Middle Element to Target

  • If nums[mid] === target, return mid — we found it.
  • If nums[mid] < target, the target must be in the right half → set left = mid + 1.
  • If nums[mid] > target, the target must be in the left half → set right = mid - 1.

4. Return -1 If Not Found

  • If the loop ends without finding the target, return -1.

🧠 Key Insight

  • Binary search works because the array is sorted: we can safely eliminate half the remaining elements at each step.
Time
O(log n)each iteration halves the search space.
Space
O(1)only a few pointer variables.

Visualization

Input:
[-1, 0, 3, 5, 9, 12], target = 9
-1001325394125
—

Press ▶ or use ← → to step through

Left (L)Right (R)ConvergedDone
6 steps

Solution Code

Next
Search in Rotated Sorted Array