Binary Search

Binary search is an efficient algorithm for finding a target value within a sorted array. This implementation includes standard binary search, lower bound, and upper bound variants.

Implementations

1. Standard Binary Search

// Binary_Search returns the index of target if found, -1 otherwise
func Binary_Search(arr []int, target int) int {
    left := 0
    right := len(arr) - 1

    for left <= right {
        mid := left + (right-left)/2
        
        if arr[mid] == target {
            return mid
        }
        
        if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

2. Lower Bound

Lower bound returns the index of the first element that is not less than the target value.

// Lower_Bound returns the index of first element >= target
func Lower_Bound(arr []int, target int) int {
    left := 0
    right := len(arr)

    for left < right {
        mid := left + (right-left)/2
        
        if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

3. Upper Bound

Upper bound returns the index of the first element that is greater than the target value.

// Upper_Bound returns the index of first element > target
func Upper_Bound(arr []int, target int) int {
    left := 0
    right := len(arr)

    for left < right {
        mid := left + (right-left)/2
        
        if arr[mid] <= target {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

Example Usage

package main

import "fmt"

func main() {
    arr := []int{1, 2, 2, 2, 3, 4, 5, 5, 6}
    target := 2

    // Standard Binary Search
    index := Binary_Search(arr, target)
    fmt.Printf("Binary Search: Found %d at index %d\n", target, index)

    // Lower Bound (first element >= target)
    lowerIdx := Lower_Bound(arr, target)
    fmt.Printf("Lower Bound: First element >= %d is at index %d\n", target, lowerIdx)

    // Upper Bound (first element > target)
    upperIdx := Upper_Bound(arr, target)
    fmt.Printf("Upper Bound: First element > %d is at index %d\n", target, upperIdx)

    // Finding count of elements equal to target
    count := upperIdx - lowerIdx
    fmt.Printf("Count of elements equal to %d: %d\n", target, count)
}

Algorithm Description

1. The algorithm works on a sorted array by:

   • Finding the middle element

   • If target equals middle element, return its position

   • If target is greater, search the right half

   • If target is smaller, search the left half

   • Repeat until target is found or search space is empty

2. Key Requirements:

   • Array must be sorted

   • Random access to elements (O(1) access time)

Time Complexity: O(log n)

• Each step reduces search space by half

• Maximum steps needed: log₂(n)

• Constant time operations in each step

Space Complexity: O(1)

• Only uses a few variables regardless of input size

• Iterative implementation uses constant space

• Recursive implementation uses O(log n) stack space

Characteristics

Advantages

1. Very efficient for large sorted datasets

2. Logarithmic time complexity

3. Simple implementation

4. Works well with cache (accessing contiguous memory)

Disadvantages

1. Requires sorted array

2. Not suitable for small arrays (linear search might be faster)

3. Requires random access to elements

Related LeetCode Problems

Easy

1. 704. Binary Search

   • Basic binary search implementation

   • Direct application of the algorithm

   • Time: O(log n), Space: O(1)

2. 35. Search Insert Position

   • Lower bound implementation

   • Find insertion position in sorted array

   • Time: O(log n), Space: O(1)

3. 69. Sqrt(x)

   • Binary search on answer space

   • Find largest number whose square ≤ x

   • Time: O(log n), Space: O(1)

Medium

1. 34. Find First and Last Position

   • Combine lower and upper bound

   • Find range of target element

   • Time: O(log n), Space: O(1)

2. 74. Search a 2D Matrix

   • Binary search on matrix

   • Convert 2D to 1D index

   • Time: O(log(m*n)), Space: O(1)

3. 162. Find Peak Element

   • Modified binary search

   • Use array property to determine search direction

   • Time: O(log n), Space: O(1)

Hard

1. 4. Median of Two Sorted Arrays

   • Binary search on smaller array

   • Partition arrays to find median

   • Time: O(log(min(m,n))), Space: O(1)

2. 1095. Find in Mountain Array

   • Binary search to find peak

   • Binary search on both sides

   • Time: O(log n), Space: O(1)

Practice Tips

1. Master the Templates:

   • Standard binary search

   • Lower bound

   • Upper bound

2. Common Patterns:

   • Search on answer space

   • Search on indices

   • Binary search on result

3. Edge Cases:

   • Empty array

   • Single element

   • Duplicate elements

   • Target not found

   • Target at boundaries

4. Implementation Tips:

   • Use left + (right-left)/2 to avoid overflow

   • Be careful with loop conditions (< vs <=)

   • Check array bounds

   • Handle duplicates correctly

Common Variations

1. Search Space:

   • Array elements

   • Answer range

   • Matrix

   • Rotated array

2. Return Value:

   • Element position

   • Insertion position

   • Range of elements

   • Boolean existence

3. Special Cases:

   • Duplicates allowed

   • Rotated array

   • Nearly sorted array

   • Infinite array

Resources

1. Binary Search Patterns

2. Visualization

3. Introduction to Algorithms (CLRS)

4. LeetCode Study Plan - Binary Search