Binary Search — Harshal

Visualize.

2

5

8

12

16

23

38

45

56

72

Step 1 / 7

Solution.

TypeScript

function binarySearch(nums: number[], target: number): number {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

My Approach.

The array is sorted — that's the detail that changes everything here. If I ignore that fact, I'd just scan left to right, O(n). But sorted data means I can ask a much sharper question at every step: is the middle element too big, too small, or exactly right?

That single comparison tells me which half of the array to throw away entirely. I don't need to look at it again.

So my approach:

Keep a window over the array — `lo` and `hi`.
Look at the middle of that window.
If it matches, I'm done.
If it's smaller than the target, the target must be somewhere to the right — so I move `lo` just past the middle.
If it's bigger, the target's to the left — move `hi` just before the middle.
Repeat until the window is empty (target isn't there) or I find it.

The thing I like about this one is how fast the search space shrinks — halving every step means even a huge array collapses to a handful of comparisons.

Example

nums = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72], target = 23

Middle starts at index 4 (16). 16 < 23, so I throw away the entire left half and everything up to and including index 4. Next middle lands right on 23. Found it in two comparisons instead of checking all ten values.

Complexity

Time: O(log n) — the search space halves every iteration
Space: O(1) — just two pointers, no extra memory