DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Binary Search

easyBinary search Must-do

Problem statement

You get an array nums of distinct integers sorted in ascending order, and a number target. Return the index of target in nums, or -1 if it is not there.

Your solution should run in O(log n) time, so scanning every element is not the intended answer.

Examples

Example 1

Input: nums = [-4, 0, 3, 8, 15, 21], target = 15

Output: 4

Explanation: nums[4] is 15.

Example 2

Input: nums = [2, 5, 9], target = 6

Output: -1

Explanation: 6 would sit between 5 and 9, but it is not in the array.

Hints

Approach

Halve the search range at every step.

  1. Set lo = 0 and hi = len(nums) - 1. The target, if present, is always inside [lo, hi].
  2. While lo <= hi:
    • compute mid = lo + (hi - lo) // 2;
    • if nums[mid] == target, return mid;
    • if nums[mid] < target, the target can only be to the right, so set lo = mid + 1;
    • otherwise set hi = mid - 1.
  3. When lo passes hi, the range is empty: return -1.

Each iteration discards half the remaining range, so there are at most about log₂(n) iterations.

ComplexityTime O(log n)Space O(1)
Python
class Solution:
def search(self, nums: list[int], target: int) -> int:
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1

Follow-up questions

  • The array may now contain duplicates. Return the first index of target.
  • Write the same search recursively, and say what it costs in stack space.

Frequently asked questions

In Java and other languages with fixed-size integers, lo + hi can overflow for very large arrays and produce a negative index. The two forms give the same result otherwise. Python integers do not overflow, but the habit carries over.

Finding the first log line after a timestamp in a sorted file, git bisect to find the commit that broke a build, and narrowing down which config change in a sequence caused an alert are all the same halving idea.

With hi = len - 1 and hi = mid - 1, use lo <= hi so a one-element range is still checked. The lo < hi form pairs with hi = mid and is used for "find the first position where" problems. Pick one template and keep its updates consistent.