⚡ Binary Search and Its Variants

Welcome back! Now that you know linear search, let’s learn Binary Search - the algorithm that can find a needle in a haystack of millions of items in just 20 steps!

2. Binary Search - The “Divide and Conquer” Champion

Imagine a phone book with 1,000,000 names. Instead of checking each name, binary search cuts the search space in half each time!

How Binary Search Works

Find 42 in: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]

Step 1: Look at middle (position 4): 50 > 42, so search left half Step 2: Left half: [10, 20, 30, 40, 50], middle (position 2): 30 < 42, search right Step 3: Right half: [40, 50], middle (position 3): 40 < 42, search right Step 4: Right half: [50], 50 > 42… not found!

// BinarySearch finds target in a sorted array by repeatedly dividing search space
func BinarySearch(arr []int, target int) int {
    left := 0
    right := len(arr) - 1

    for left <= right {
        // Find middle (avoid overflow with this formula)
        middle := left + (right - left) / 2

        if arr[middle] == target {
            return middle  // Found it!
        } else if arr[middle] < target {
            left = middle + 1  // Search right half
        } else {
            right = middle - 1  // Search left half
        }
    }

    return -1  // Not found
}

Requirements: Data must be sorted Speed: O(log n) - incredibly fast! Best for: Large sorted datasets

Binary Search with Bounds

Sometimes you want to find the first or last occurrence:

// BinarySearchFirst finds the first occurrence of target
func BinarySearchFirst(arr []int, target int) int {
    left := 0
    right := len(arr) - 1
    result := -1

    for left <= right {
        middle := left + (right - left) / 2

        if arr[middle] == target {
            result = middle  // Found, but keep searching left for first occurrence
            right = middle - 1
        } else if arr[middle] < target {
            left = middle + 1
        } else {
            right = middle - 1
        }
    }

    return result
}

3. Exponential Search - The “Jump Start” Method

What if you don’t know where to start binary search? Exponential search finds the right range first, then uses binary search!

How Exponential Search Works

Find 75 in: [1, 2, 4, 8, 16, 32, 64, 128, 256, 512]

Step 1: Find the range (exponential jumps)

• Check position 1: 2 < 75, jump to 2
• Check position 2: 4 < 75, jump to 4
• Check position 4: 16 < 75, jump to 8
• Check position 8: 128 > 75, stop! Range is 4-8

Step 2: Binary search in range [16, 32, 64, 128]

import "math"

// ExponentialSearch finds range with exponential jumps, then binary searches
func ExponentialSearch(arr []int, target int) int {
    n := len(arr)

    // If first element is target
    if arr[0] == target {
        return 0
    }

    // Find range with exponential jumps
    i := 1
    for i < n && arr[i] <= target {
        i *= 2  // Double the jump size
    }

    // Now binary search between i/2 and min(i, n-1)
    left := i / 2
    right := int(math.Min(float64(i), float64(n-1)))

    return BinarySearchInRange(arr, target, left, right)
}

// Helper function for binary search in a specific range
func BinarySearchInRange(arr []int, target, left, right int) int {
    for left <= right {
        middle := left + (right - left) / 2

        if arr[middle] == target {
            return middle
        } else if arr[middle] < target {
            left = middle + 1
        } else {
            right = middle - 1
        }
    }
    return -1
}

Best for: When you have no idea where the item is, but data is sorted Speed: Almost as fast as binary search

4. Interpolation Search - The “Smart Guess” Method

Imagine a phone book with names from “Anderson” to “Zimmerman”. If you’re looking for “Smith”, you don’t open to the middle! You guess it should be about 80% through the book.

How Interpolation Search Works

Find 75 in: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]

Step 1: Make a smart guess

• Numbers range from 10 to 100
• Looking for 75
• Guess position: 10 + ((75-10) × (10-0) / (100-10)) = position ~6.5 → check position 6

Step 2: Check position 6: 70

• 70 < 75, so search right half: [80, 90, 100]

Step 3: Guess again in smaller range

• Range 80-100, looking for 75… wait, 75 is too small! Not in this range.

// InterpolationSearch guesses where the target should be based on its value
func InterpolationSearch(arr []int, target int) int {
    left := 0
    right := len(arr) - 1

    // Keep searching while target is in range and we have items left
    for left <= right && target >= arr[left] && target <= arr[right] {
        if left == right {
            if arr[left] == target {
                return left
            }
            return -1
        }

        // Smart guess: where should target be?
        // Formula: left + ((target - arr[left]) * (right - left) / (arr[right] - arr[left]))
        positionGuess := left + ((target - arr[left]) * (right - left) / (arr[right] - arr[left]))

        if arr[positionGuess] == target {
            return positionGuess
        } else if arr[positionGuess] < target {
            left = positionGuess + 1   // Search right half
        } else {
            right = positionGuess - 1  // Search left half
        }
    }

    return -1
}

Best for: Numbers that are evenly spread out (like 1, 2, 3, 4, 5…) Worst for: Numbers in clumps (like 1, 1, 1, 50, 50, 50…) Speed: Can be faster than binary search for evenly distributed data!

5. Jump Search - The “Block Jump” Method

Imagine a long book divided into chapters. Instead of reading every page, you jump from chapter to chapter until you find the right section, then read page-by-page in that chapter.

How Jump Search Works

Find 42 in: [5, 12, 18, 25, 30, 42, 55, 67, 73, 89]

Step 1: Jump ahead in blocks

• Block size = √10 ≈ 3
• Jump 1: Check position 3 (25) < 42, jump to 6
• Jump 2: Check position 6 (42) = 42, FOUND!

Step 2: If not exact match, search within the block

• If we jumped too far, go back one block and search linearly

import "math"

// JumpSearch jumps ahead in blocks, then searches within the block
func JumpSearch(arr []int, target int) int {
    n := len(arr)
    // Block size is square root of array size (optimal)
    blockSize := int(math.Sqrt(float64(n)))
    prev := 0  // Where previous jump landed

    // Jump ahead in blocks
    for arr[min(blockSize, n)-1] < target {
        prev = blockSize
        blockSize += int(math.Sqrt(float64(n)))  // Next block

        if prev >= n {
            return -1  // Jumped past end
        }
    }

    // Now search linearly within the found block
    for i := prev; i < min(blockSize, n); i++ {
        if arr[i] == target {
            return i
        }
    }

    return -1
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Good balance: Faster than linear search, simpler than binary search Speed: Between linear and binary search

6. Fibonacci Search - The “Nature’s Sequence” Method

Remember the Fibonacci sequence? 1, 1, 2, 3, 5, 8, 13, 21… Nature uses this sequence everywhere (pineapple spirals, flower petals). Fibonacci Search uses these special numbers to divide the search space!

How Fibonacci Search Works

Find 42 in: [5, 12, 18, 25, 30, 42, 55, 67, 73, 89]

Step 1: Find Fibonacci numbers around array size

• Array has 10 items
• Find Fib numbers: 8, 13 (13 > 10, 8 < 10)
• Use Fib(8) = 21, Fib(7) = 13, Fib(6) = 8

Step 2: Compare at Fib positions

• Check position 7 (0-based): arr[7] = 67
• 67 > 42, so search left half (positions 0-6)

Step 3: Continue with smaller Fib numbers

• Like binary search, but using Fib ratios

// FibonacciSearch uses Fibonacci sequence to divide the search space
func FibonacciSearch(arr []int, target int) int {
    n := len(arr)

    // Initialize Fibonacci numbers
    fib2 := 0  // (m-2)th Fibonacci number
    fib1 := 1  // (m-1)th Fibonacci number
    fib := fib2 + fib1  // mth Fibonacci number

    // Find smallest Fibonacci number >= n
    for fib < n {
        fib2 = fib1
        fib1 = fib
        fib = fib2 + fib1
    }

    // Offset for eliminated range
    offset := -1

    // Search using Fibonacci divisions
    for fib > 1 {
        // Check if fib2 is valid index
        i := min(offset + fib2, n-1)

        if arr[i] < target {
            // Search upper half
            fib = fib1
            fib1 = fib2
            fib2 = fib - fib1
            offset = i
        } else if arr[i] > target {
            // Search lower half
            fib = fib2
            fib1 = fib1 - fib2
            fib2 = fib - fib1
        } else {
            // Found it!
            return i
        }
    }

    // Check last possible position
    if fib1 == 1 && arr[offset+1] == target {
        return offset + 1
    }

    return -1
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Why Fibonacci? It divides the array in ratios that are close to the golden ratio (nature’s perfect division!) Speed: Similar to binary search

Search Method Comparison - Which to Use When?

Practice Challenges - Level Up Your Skills!

1. Rotated Array Search: Search in a sorted array that was rotated (like [4,5,6,1,2,3])
2. First Bad Version: Find the first version that introduced a bug in a sequence of versions
3. Peak Finder: Find the peak element in an array (larger than neighbors)
4. Range Search: Find all elements within a given range [low, high]

Key Takeaways - Binary Search Mastery

• Binary search cuts search space in half each time - O(log n) speed!
• Requires sorted data - that’s the trade-off for speed
• Many variants exist for different data distributions and use cases
• Interpolation search can be faster for evenly distributed data
• Jump search offers a good balance of speed and simplicity

Next: Discover real-world applications and advanced search techniques! 🌟

Ready to see searching in action? Let’s explore real-world applications! 🚀