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

Binary Search

Guide 1 of 6 · Path 1 of 6

PreviousNext →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumbinary-search

Search in Rotated Sorted Array

Problem (restated)

A sorted array of distinct values was rotated at an unknown pivot. Given nums and target, return the index of target, or -1 if missing. Must run in O(log n).

Intuition

At least one half of [lo,hi] is sorted. Check which half is sorted and whether target lies in it; discard the other half.

Approaches

Binary search on rotated array

Tested only
Time O(log n)Space O(1)

Idea. While lo≤hi, mid = … If nums[mid]==target return mid. If left half sorted, search left if target in range else right; symmetrically for right half.

Walkthrough. [4,5,6,7,0,1,2], target=0 → eventually mid lands near pivot side and finds 0.

Trade-offs. Careful with ≤ on boundaries. Duplicates (LC 81) need a different shrink step.

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

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

Template connection

Binary search with an extra check for which side is monotonic.

Reflection