Leetcode/Guide/Binary Search

Contents

Binary Search is one of the most fundamental and efficient algorithms for searching in a sorted array.
Instead of scanning every element, it repeatedly divides the search range in half — achieving O(log n) time complexity.

---

🧠 Core Idea

• Works only on sorted data (ascending or descending).
• Use two pointers:
  • leftIndex (start of the range)
  • rightIndex (end of the range)
• Repeatedly:
  1. Find the middle index.
  2. Compare the middle value with the target.
  3. Move either the left or right pointer inward based on comparison.

---

Example 1 — Basic Binary Search (Ascending Array)

function binarySearch(sortedNumbers, targetValue) {
  let leftIndex = 0;
  let rightIndex = sortedNumbers.length - 1;

  while (leftIndex <= rightIndex) {
    const middleIndex = Math.floor((leftIndex + rightIndex) / 2);
    const middleValue = sortedNumbers[middleIndex];

    if (middleValue === targetValue) {
      return middleIndex;
    }

    if (middleValue < targetValue) {
      leftIndex = middleIndex + 1; // search right half
    } else {
      rightIndex = middleIndex - 1; // search left half
    }
  }

  return -1; // not found
}

// Demo
console.log(binarySearch([1, 3, 5, 7, 9, 11], 7));  // 3
console.log(binarySearch([1, 3, 5, 7, 9, 11], 4));  // -1

✅ Why this works:
We eliminate half of the remaining elements each time by checking the middle value — giving us logarithmic efficiency.

---

Example 2 — Find First Occurrence of a Target

In arrays with duplicates, a normal binary search might return any occurrence.
This version ensures we return the first position.

function findFirstOccurrence(sortedNumbers, targetValue) {
  let leftIndex = 0;
  let rightIndex = sortedNumbers.length - 1;
  let firstOccurrenceIndex = -1;

  while (leftIndex <= rightIndex) {
    const middleIndex = Math.floor((leftIndex + rightIndex) / 2);
    const middleValue = sortedNumbers[middleIndex];

    if (middleValue === targetValue) {
      firstOccurrenceIndex = middleIndex;
      rightIndex = middleIndex - 1; // keep searching left side
    } else if (middleValue < targetValue) {
      leftIndex = middleIndex + 1;
    } else {
      rightIndex = middleIndex - 1;
    }
  }

  return firstOccurrenceIndex;
}

// Demo
console.log(findFirstOccurrence([1, 2, 2, 2, 3, 4], 2)); // 1

✅ Why this works:
Even after finding the target, we continue searching the left half for earlier occurrences.

---

Example 3 — Find Insertion Index (Lower Bound)

Sometimes you need to find where a number should be inserted to keep the array sorted.

function findInsertionIndex(sortedNumbers, targetValue) {
  let leftIndex = 0;
  let rightIndex = sortedNumbers.length;

  while (leftIndex < rightIndex) {
    const middleIndex = Math.floor((leftIndex + rightIndex) / 2);
    if (sortedNumbers[middleIndex] < targetValue) {
      leftIndex = middleIndex + 1;
    } else {
      rightIndex = middleIndex;
    }
  }

  return leftIndex; // position to insert
}

// Demo
console.log(findInsertionIndex([1, 3, 5, 7], 4)); // 2
console.log(findInsertionIndex([1, 3, 5, 7], 8)); // 4

✅ Why this works:
We narrow the range until leftIndex is the first position where the target could go.

---

Example 4 — Binary Search (Descending Array)

You can also use binary search on a descending array with reversed comparisons.

function binarySearchDescending(sortedNumbers, targetValue) {
  let leftIndex = 0;
  let rightIndex = sortedNumbers.length - 1;

  while (leftIndex <= rightIndex) {
    const middleIndex = Math.floor((leftIndex + rightIndex) / 2);
    const middleValue = sortedNumbers[middleIndex];

    if (middleValue === targetValue) {
      return middleIndex;
    }

    if (middleValue > targetValue) {
      leftIndex = middleIndex + 1; // search right half (since it's smaller)
    } else {
      rightIndex = middleIndex - 1; // search left half
    }
  }

  return -1;
}

// Demo
console.log(binarySearchDescending([9, 7, 5, 3, 1], 5)); // 2

✅ Why this works:
We flip the comparison logic since larger values are on the left.

---

Example 5 — Search in Rotated Sorted Array

A common coding test question.
Even if the array was sorted but rotated (like [4,5,6,7,0,1,2]), we can still apply binary search logic.

function searchInRotatedSortedArray(numbers, targetValue) {
  let leftIndex = 0;
  let rightIndex = numbers.length - 1;

  while (leftIndex <= rightIndex) {
    const middleIndex = Math.floor((leftIndex + rightIndex) / 2);
    const middleValue = numbers[middleIndex];

    if (middleValue === targetValue) return middleIndex;

    // Left half is sorted
    if (numbers[leftIndex] <= middleValue) {
      if (targetValue >= numbers[leftIndex] && targetValue < middleValue) {
        rightIndex = middleIndex - 1;
      } else {
        leftIndex = middleIndex + 1;
      }
    } else {
      // Right half is sorted
      if (targetValue > middleValue && targetValue <= numbers[rightIndex]) {
        leftIndex = middleIndex + 1;
      } else {
        rightIndex = middleIndex - 1;
      }
    }
  }

  return -1;
}

// Demo
console.log(searchInRotatedSortedArray([4, 5, 6, 7, 0, 1, 2], 0)); // 4

✅ Why this works:
We detect which half is sorted at each step, then decide which side to search in.

---

🧩 Summary Table

---

🚀 Key Takeaways

• Binary search requires sorted input.
• Reduces time complexity from O(n) to O(log n).
• Uses two pointers (leftIndex, rightIndex) and a middleIndex.
• Common applications:
  • Searching
  • Range queries
  • Finding boundaries (first/last occurrence, insertion points)

Mastering binary search and its variations is essential for coding interviews and performance-critical algorithms.