Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Binary Search

Guide 6 of 6 · Path 6 of 6

← PreviousNext pattern: Binary Search on Answer →

Interactive

Mental model

A worked animation for this problem. Scrub steps or press space to pause; re-tell the invariant out loud.

Step 1 of 8
-1
lo
0
3
5
mid
9
12

a[mid] = 5

Half-open search space [lo, hi). Target = 9.

Easybinary-search

Binary Search

Problem (restated)

Given a sorted array of distinct integers and a target, return the index of target or -1.

Intuition

Classic lower-bound binary search on a sorted array.

Approaches

Lower-bound binary search

Verified
Time O(log n)Space O(1)

Idea. lo=0, hi=n exclusive; while lo<hi mid=…; if nums[mid]<target lo=mid+1 else hi=mid. Check nums[lo].

Walkthrough. nums=[-1,0,3,5,9,12], target=9 → index 4.

Trade-offs. Iterative form avoids recursion depth concerns.

Solution
export function search(nums: number[], target: number): number {
  let lo = 0, hi = nums.length;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid]! < target) lo = mid + 1;
    else hi = mid;
  }
  return lo < nums.length && nums[lo] === target ? lo : -1;
}

export function search(nums: number[], target: number): number {
  let lo = 0, hi = nums.length;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid]! < target) lo = mid + 1;
    else hi = mid;
  }
  return lo < nums.length && nums[lo] === target ? lo : -1;
}

Template connection

Direct application of the Binary Search template.

Reflection