The Runtime Theory
easyLeetCode#binary-search#iterative

Implement Binary Search

Implement binary search that finds a target value in a sorted array in O(log n) time.

The Runtime Theory Team1 min read
Solve it

Solving happens on the judge — come back and mark it done

Sample cases

innums = [-1,0,3,5,9,12], target = 9

out4

innums = [-1,0,3,5,9,12], target = 2

out-1

innums = [1], target = 1

out0

Implement Binary Search

Write a function that, given a sorted array of integers and a target value, returns the index of the target, or -1 if not found.

Requirements

  • Time complexity: O(log n)
  • Space complexity: O(1) (iterative solution)
  • Array is sorted in ascending order, no duplicates

Hints

  1. Set low = 0 and high = len(nums) - 1.
  2. Compute mid = (low + high) // 2.
  3. If nums[mid] == target, return mid.
  4. If nums[mid] < target, set low = mid + 1. If nums[mid] > target, set high = mid - 1.
  5. Repeat until low > high.

The key gotcha: you must adjust low or high to mid + 1 or mid - 1 (not just mid) to avoid infinite loops.

Read: Arrays and Memory · Trace: Linear Search

More practice in this topic

easy · programming algorithmsFind the First Valid Position

One dispatch a week

The trace behind each problem, the tradeoff that explains it, and one technical dispatch per week — no noise.

One technical dispatch per week. No noise.

Not started

Sign in to save your learning progress.

Sign in to save