🗓️ Day 13: Binary Search Basics

🧠 Concept Deep Dive

Binary Search is a powerful and efficient algorithm to find an element in a sorted array. Instead of scanning every element like linear search (O(n)), binary search repeatedly divides the array in half, drastically reducing the search space — achieving O(log n) time complexity.

🔹 When to Use Binary Search

• The array (or search space) must be sorted.
• You're searching for a specific value or condition.

🔹 How It Works

1. Initialize low = 0 and high = arr.length - 1
2. While low <= high:
   • Compute the middle: mid = Math.floor((low + high) / 2)
   • Compare arr[mid] to the target:
     • If equal, return mid
     • If target < arr[mid], move to left half (high = mid - 1)
     • Else, move to right half (low = mid + 1)

📖 Example 1: Basic Binary Search

Problem:

Find the index of a target number in a sorted array.

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

Example:

Input: nums = [1, 3, 5, 7, 9], target = 5
Output: 2  // 5 is at index 2

📖 Example 2: Lower Bound (First Occurrence ≥ target)

Use binary search to find the first number in the array that is greater than or equal to a given target.

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

Example:

Input: nums = [1, 2, 4, 4, 5, 6], target = 4
Output: 2  // index of first 4

🔬 Real-world Analogy

Imagine you're looking for a word in a dictionary. You don't check each word one by one — instead, you open the book near the middle, check the word, and decide whether to look in the earlier or later pages. That’s binary search!

📊 Big O Complexity

🧪 LeetCode-style Homework

Problem: Guess Number Higher or Lower

You are trying to guess a number between 1 and n. Each time you guess, a function tells you if your guess is too high, too low, or correct.

function guessNumber(n: number): number {
  let low = 1, high = n;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    const res = guess(mid); // Provided API
    if (res === 0) return mid;
    else if (res < 0) high = mid - 1;
    else low = mid + 1;
  }
  return -1;
}

Note: You are given the guess(num: number): number API.

Example:

Input: n = 10, pick = 6
Output: 6

🗓️ Summary

• Binary Search is efficient for sorted data
• Reduces time from O(n) to O(log n)
• Variants include finding lower/upper bounds, first/last positions, etc.

🔮 Up Next

▶️ Day 14: Binary Search Variants (Lower Bound, Upper Bound, First/Last Occurrence)