🗓️ Day 6: Binary Search Fundamentals

🧐 Concept Deep Dive

Binary Search is a classic algorithm that dramatically reduces search time in sorted arrays. Instead of scanning the array linearly, it repeatedly divides the search space in half.

🔹 Why Binary Search?

If you have a sorted array and need to search for a target value, a linear search takes O(n) time. Binary search improves this to O(log n), which is much faster for large inputs.

🔹 How It Works:

Given a sorted array, and a target:

• Start with left = 0, right = arr.length - 1
• While left <= right:
  • Calculate mid = Math.floor((left + right) / 2)
  • If arr[mid] === target, return mid
  • If arr[mid] < target, search right half: left = mid + 1
  • Else search left half: right = mid - 1

📖 Code Example: Basic Binary Search

function binarySearch(arr: number[], target: number): number {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1; // Not found
}

// Test
console.log(binarySearch([1, 3, 5, 7, 9], 5)); // Output: 2
console.log(binarySearch([1, 3, 5, 7, 9], 6)); // Output: -1

📊 Visualization

Array:       [1, 3, 5, 7, 9]
Indexes:      0  1  2  3  4
Target: 5

First:  mid = 2, arr[2] = 5 → found it!

😍 Real-world Analogy: Guess the Number Game

Imagine someone thinks of a number from 1 to 100, and you guess it. Every time, they tell you if the number is higher or lower than your guess. That process is binary search in action!

🔧 Binary Search Variants

• First Occurrence / Last Occurrence in sorted array with duplicates
• Search in Rotated Sorted Array
• Search Insert Position
• Binary Search on Answer (advanced)

We'll explore these in coming days.

🔮 Big O Complexity

🧪 LeetCode-style Homework

Problem: Basic Binary Search

Function Signature:

function search(nums: number[], target: number): number;

Input:

nums = [-1,0,3,5,9,12], target = 9

Output:

4

Explanation: 9 is at index 4 in the array.

Bonus: Try implementing recursive binary search too!

📆 Summary

• Binary Search is a must-know algorithm for efficient searching in sorted data
• Operates in O(log n) time
• Foundation for many interview questions and real-world systems

🔬 Up Next

▶️ Day 6: First and Last Position in Sorted Array — Let’s handle duplicate values using binary search variants!