Binary Search

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the search interval in half, comparing the target with the middle element, and eliminating half of the remaining elements in each step.

Algorithm Overview

Binary search uses a divide-and-conquer approach with a key requirement: the input array must be sorted. The algorithm maintains two pointers (left and right) and repeatedly calculates the middle element. Based on the comparison with the target, it eliminates half of the search space in each iteration.

Key Features

Efficient: O(log n) time complexity
Predictable Performance: Consistent logarithmic behavior
Multiple Variants: Specialized implementations for different use cases
Sorted Data Requirement: Only works on sorted arrays
Optimal for Large Datasets: Performance advantage increases with data size

Time and Space Complexity

Time Complexity: O(log n) where n is the number of elements
Space Complexity:
O(1) for iterative implementation
O(log n) for recursive implementation (due to call stack)
Best Case: O(1) - target is the middle element
Worst Case: O(log n) - consistent performance
Average Case: O(log n) - consistent performance

Usage Examples

Basic Usage

from algo.algorithms.searching.binary_search import binary_search

# Simple search in sorted array
data = [1, 3, 5, 7, 9, 11, 13, 15]
index = binary_search(data, 7)
print(f"Found 7 at index: {index}")  # Output: Found 7 at index: 3

# Search in sorted strings
names = ['Alice', 'Bob', 'Charlie', 'David']
index = binary_search(names, 'Charlie')
print(f"Found Charlie at index: {index}")  # Output: Found Charlie at index: 2

# Target not found
index = binary_search(data, 6)
print(f"6 not found: {index}")  # Output: 6 not found: -1

Handling Duplicates

from algo.algorithms.searching.binary_search import (
    binary_search_leftmost, binary_search_rightmost, binary_search_range
)

# Array with duplicates
data = [1, 2, 2, 2, 3, 4, 4, 5]

# Find first occurrence
first = binary_search_leftmost(data, 2)
print(f"First occurrence of 2: {first}")  # Output: First occurrence of 2: 1

# Find last occurrence
last = binary_search_rightmost(data, 2)
print(f"Last occurrence of 2: {last}")  # Output: Last occurrence of 2: 3

# Find range of all occurrences
start, end = binary_search_range(data, 2)
print(f"All occurrences of 2: indices {start} to {end}")  # Output: All occurrences of 2: indices 1 to 3

Insert Position

from algo.algorithms.searching.binary_search import binary_search_insert_position

# Find where to insert elements to maintain sort order
data = [1, 3, 5, 6]

positions = []
for target in [2, 4, 7, 0]:
    pos = binary_search_insert_position(data, target)
    positions.append((target, pos))
    print(f"Insert {target} at position {pos}")

# Output:
# Insert 2 at position 1
# Insert 4 at position 2  
# Insert 7 at position 4
# Insert 0 at position 0

Conditional Search

from algo.algorithms.searching.binary_search import binary_search_with_condition

# Find first element satisfying a condition
data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

# Find first even number >= 6
index = binary_search_with_condition(data, lambda x: x >= 6 and x % 2 == 0)
print(f"First even number >= 6 at index: {index}")  # Output: First even number >= 6 at index: 5

# Find first element > threshold
threshold = 7
index = binary_search_with_condition(data, lambda x: x > threshold)
print(f"First element > {threshold} at index: {index}")  # Output: First element > 7 at index: 7

Find Closest Element

from algo.algorithms.searching.binary_search import binary_search_closest

# Find element closest to target
data = [1, 3, 5, 7, 9, 11, 13, 15]

targets = [4, 6, 8, 12, 20]
for target in targets:
    index = binary_search_closest(data, target)
    closest_value = data[index]
    print(f"Closest to {target}: {closest_value} at index {index}")

# Output:
# Closest to 4: 3 at index 1 (or 5 at index 2, implementation may vary)
# Closest to 6: 5 at index 2 (or 7 at index 3)
# Closest to 8: 7 at index 3 (or 9 at index 4)
# Closest to 12: 11 at index 5 (or 13 at index 6)
# Closest to 20: 15 at index 7

2D Matrix Search

from algo.algorithms.searching.binary_search import binary_search_2d

# Search in row/column sorted matrix
matrix = [
    [1,  4,  7,  11],
    [2,  5,  8,  12],
    [3,  6,  9,  16],
    [10, 13, 14, 17]
]

# Find element in matrix
row, col = binary_search_2d(matrix, 6)
print(f"Found 6 at position ({row}, {col})")  # Output: Found 6 at position (2, 1)

# Element not found
row, col = binary_search_2d(matrix, 15)
print(f"15 not found: ({row}, {col})")  # Output: 15 not found: (-1, -1)

Recursive vs Iterative

from algo.algorithms.searching.binary_search import binary_search, binary_search_recursive

data = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 11

# Both should give same result
iterative_result = binary_search(data, target)
recursive_result = binary_search_recursive(data, target)

print(f"Iterative result: {iterative_result}")  # Output: Iterative result: 5
print(f"Recursive result: {recursive_result}")   # Output: Recursive result: 5
print(f"Results match: {iterative_result == recursive_result}")  # Output: Results match: True

Performance Characteristics

Efficiency Comparison

Binary search's logarithmic time complexity provides significant performance advantages over linear search as data size increases:

import time
from algo.algorithms.searching.binary_search import binary_search
from algo.algorithms.searching.linear_search import linear_search

# Performance comparison
def compare_search_performance(size):
    # Create sorted data
    data = list(range(size))
    target = size // 2

    # Time linear search
    start = time.time()
    for _ in range(1000):
        linear_search(data, target)
    linear_time = time.time() - start

    # Time binary search
    start = time.time()
    for _ in range(1000):
        binary_search(data, target)
    binary_time = time.time() - start

    speedup = linear_time / binary_time if binary_time > 0 else float('inf')
    print(f"Size {size:6d}: Linear={linear_time:.4f}s, Binary={binary_time:.4f}s, Speedup={speedup:.1f}x")

# Test with different sizes
for size in [100, 1000, 10000, 100000]:
    compare_search_performance(size)

Scalability

Data Size	Linear Search	Binary Search	Speedup
100	~50 comparisons	~7 comparisons	7x
1,000	~500 comparisons	~10 comparisons	50x
10,000	~5,000 comparisons	~14 comparisons	357x
100,000	~50,000 comparisons	~17 comparisons	2,941x
1,000,000	~500,000 comparisons	~20 comparisons	25,000x

Data Type Support

Binary search works with any data type that supports comparison operators:

# Numbers
binary_search([1, 2, 3, 4, 5], 3)

# Strings (lexicographic order)
binary_search(['apple', 'banana', 'cherry', 'date'], 'cherry')

# Floats
binary_search([1.1, 2.2, 3.3, 4.4, 5.5], 3.3)

# Custom objects with comparison methods
class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __eq__(self, other):
        return isinstance(other, Person) and self.age == other.age

    def __lt__(self, other):
        return isinstance(other, Person) and self.age < other.age

    def __le__(self, other):
        return isinstance(other, Person) and self.age <= other.age

# Sorted by age
people = [Person('Alice', 25), Person('Bob', 30), Person('Charlie', 35)]
target = Person('Someone', 30)
index = binary_search(people, target)  # Finds Bob

Algorithm Requirements

Sorted Data Requirement

The most critical requirement for binary search is that the input array must be sorted:

# ✅ Correct usage - sorted array
sorted_data = [1, 3, 5, 7, 9]
result = binary_search(sorted_data, 5)  # Works correctly

# ❌ Incorrect usage - unsorted array  
unsorted_data = [3, 1, 5, 9, 7]
result = binary_search(unsorted_data, 5)  # Undefined behavior, may return wrong result

# ✅ Solution - sort first if needed
unsorted_data = [3, 1, 5, 9, 7]
sorted_data = sorted(unsorted_data)
result = binary_search(sorted_data, 5)  # Now works correctly

Comparison Operations

Elements must support the required comparison operations:

# For basic binary search: ==, <, >
# For advanced variants: <=, >=

class ComparableItem:
    def __init__(self, value):
        self.value = value

    def __eq__(self, other):
        return self.value == other.value

    def __lt__(self, other):
        return self.value < other.value

    def __le__(self, other):
        return self.value <= other.value

Edge Cases and Error Handling

Binary search handles various edge cases:

# Empty array
result = binary_search([], 5)  # Returns -1

# Single element - found
result = binary_search([42], 42)  # Returns 0

# Single element - not found
result = binary_search([42], 5)  # Returns -1

# All elements the same
result = binary_search([5, 5, 5, 5, 5], 5)  # Returns any valid index

# Target smaller than all elements
result = binary_search([10, 20, 30], 5)  # Returns -1

# Target larger than all elements
result = binary_search([10, 20, 30], 50)  # Returns -1

Best Practices

Ensure sorted data: Always verify your input array is sorted
Choose appropriate variant: Use specialized functions for specific needs
Handle edge cases: Check for -1 return values and empty arrays
Consider preprocessing cost: Factor in sorting time for overall performance
Use built-in functions: Consider Python's bisect module for production code
Profile performance: Measure actual performance in your specific use case

Common Pitfalls

Unsorted data: Using binary search on unsorted arrays gives incorrect results
Integer overflow: Use mid = left + (right - left) // 2 instead of mid = (left + right) // 2
Infinite loops: Ensure loop termination conditions are correct
Off-by-one errors: Be careful with boundary conditions and inclusive/exclusive ranges
Comparison inconsistency: Ensure comparison operators are implemented correctly for custom objects

Algorithm Variants Summary

Function	Use Case	Returns	Requirements
`binary_search`	Find any occurrence	Index or -1	Sorted array
`binary_search_recursive`	Recursive implementation	Index or -1	Sorted array
`binary_search_leftmost`	Find first occurrence	Index or -1	Sorted array
`binary_search_rightmost`	Find last occurrence	Index or -1	Sorted array
`binary_search_range`	Find all occurrences range	(start, end) or (-1, -1)	Sorted array
`binary_search_insert_position`	Find insertion point	Index	Sorted array
`binary_search_with_condition`	Custom conditions	Index or -1	Sorted array
`binary_search_closest`	Find nearest element	Index	Sorted array
`binary_search_builtin`	Using bisect module	Index or -1	Sorted array
`binary_search_2d`	2D matrix search	(row, col) or (-1, -1)	Row/col sorted matrix

When to Use Binary Search

Ideal Scenarios

Large sorted datasets (>1000 elements)
Frequent searches on the same data
When search performance is critical
Data that's naturally maintained in sorted order

Consider Alternatives When

Data is small (<100 elements)
Data changes frequently (high insert/delete rate)
Data cannot be sorted
Memory is extremely constrained
Simple implementation is more important than performance

API Reference

Binary Search Algorithm Implementation

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the search interval in half. If the value is less than the item in the middle of the interval, it narrows the interval to the lower half. Otherwise, it narrows it to the upper half. The search continues until the value is found or the interval is empty.

Key Features:

Standard binary search
Recursive implementation
Find leftmost/rightmost occurrence
Search for range of values
Insert position finding

Time Complexity: O(log n)

Space Complexity: O(1) for iterative, O(log n) for recursive

Requirements:

Input array must be sorted in ascending order
Elements must be comparable

`binary_search(arr, target)`

Perform binary search on a sorted array.

Parameters:

Name	Type	Description	Default
`arr`	`List[T]`	Sorted list of elements to search through	required
`target`	`T`	Value to search for	required

Returns:

Type	Description
`int`	Index of target if found, -1 if not found

Examples:

>>> binary_search([1, 3, 5, 7, 9], 5)
2
>>> binary_search([1, 3, 5, 7, 9], 4)
-1
>>> binary_search([], 1)
-1

`binary_search_2d(matrix, target)`

Search for target in a 2D matrix where each row and column is sorted.

This assumes the matrix is sorted both row-wise and column-wise.

Parameters:

Name	Type	Description	Default
`matrix`	`List[List[T]]`	2D list where each row and column is sorted	required
`target`	`T`	Value to search for	required

Returns:

Type	Description
`Tuple[int, int]`	Tuple of (row, col) if found, (-1, -1) if not found

Examples:

>>> matrix = [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
>>> binary_search_2d(matrix, 5)
(1, 1)
>>> binary_search_2d(matrix, 10)
(-1, -1)

`binary_search_builtin(arr, target)`

Binary search using Python's built-in bisect module.

This is provided for comparison and demonstrates how to use the standard library for binary search operations.

Parameters:

Name	Type	Description	Default
`arr`	`List[T]`	Sorted list of elements	required
`target`	`T`	Value to search for	required

Returns:

Type	Description
`int`	Index of target if found, -1 if not found

Examples:

>>> binary_search_builtin([1, 3, 5, 7, 9], 5)
2
>>> binary_search_builtin([1, 3, 5, 7, 9], 4)
-1

`binary_search_closest(arr, target)`

Find the element closest in value to the target.

Parameters:

Name	Type	Description	Default
`arr`	`List[T]`	Sorted list of elements	required
`target`	`T`	Value to find closest match for	required

Returns:

Type	Description
`int`	Index of element closest to target

Examples:

>>> binary_search_closest([1, 3, 5, 7, 9], 4)
1  # 3 is closest to 4
>>> binary_search_closest([1, 3, 5, 7, 9], 6)
2  # Both 5 and 7 are equally close, returns leftmost

`binary_search_insert_position(arr, target)`

Find the position where target should be inserted to keep array sorted.

If target already exists, returns the position of the leftmost occurrence.

Parameters:

Name	Type	Description	Default
`arr`	`List[T]`	Sorted list of elements	required
`target`	`T`	Value to find insertion position for	required

Returns:

Type	Description
`int`	Index where target should be inserted

Examples:

>>> binary_search_insert_position([1, 3, 5, 6], 5)
2
>>> binary_search_insert_position([1, 3, 5, 6], 2)
1
>>> binary_search_insert_position([1, 3, 5, 6], 7)
4
>>> binary_search_insert_position([1, 3, 5, 6], 0)
0

`binary_search_leftmost(arr, target)`

Find the leftmost (first) occurrence of target in a sorted array.

This is useful when the array contains duplicate values and you want to find the first occurrence.

Parameters:

Name	Type	Description	Default
`arr`	`List[T]`	Sorted list of elements (may contain duplicates)	required
`target`	`T`	Value to search for	required

Returns:

Type	Description
`int`	Index of leftmost occurrence, -1 if not found

Examples:

>>> binary_search_leftmost([1, 2, 2, 2, 3], 2)
1
>>> binary_search_leftmost([1, 1, 1, 1, 1], 1)
0
>>> binary_search_leftmost([1, 3, 5], 2)
-1

`binary_search_range(arr, target)`

Find the range of indices where target appears in a sorted array.

Returns the first and last positions of the target value.

Parameters:

Name	Type	Description	Default
`arr`	`List[T]`	Sorted list of elements (may contain duplicates)	required
`target`	`T`	Value to search for	required

Returns:

Type	Description
`Tuple[int, int]`	Tuple of (first_index, last_index) or (-1, -1) if not found

Examples:

>>> binary_search_range([1, 2, 2, 2, 3], 2)
(1, 3)
>>> binary_search_range([1, 3, 5], 2)
(-1, -1)
>>> binary_search_range([5, 5, 5], 5)
(0, 2)

`binary_search_recursive(arr, target, left=0, right=None)`

Recursive implementation of binary search.

Parameters:

Name	Type	Description	Default
`arr`	`List[T]`	Sorted list of elements to search through	required
`target`	`T`	Value to search for	required
`left`	`int`	Left boundary of search range	`0`
`right`	`Optional[int]`	Right boundary of search range (None means end of array)	`None`

Returns:

Type	Description
`int`	Index of target if found, -1 if not found

Examples:

>>> binary_search_recursive([1, 3, 5, 7, 9], 7)
3
>>> binary_search_recursive([1, 3, 5, 7, 9], 2)
-1

`binary_search_rightmost(arr, target)`

Find the rightmost (last) occurrence of target in a sorted array.

This is useful when the array contains duplicate values and you want to find the last occurrence.

Parameters:

Name	Type	Description	Default
`arr`	`List[T]`	Sorted list of elements (may contain duplicates)	required
`target`	`T`	Value to search for	required

Returns:

Type	Description
`int`	Index of rightmost occurrence, -1 if not found

Examples:

>>> binary_search_rightmost([1, 2, 2, 2, 3], 2)
3
>>> binary_search_rightmost([1, 1, 1, 1, 1], 1)
4
>>> binary_search_rightmost([1, 3, 5], 2)
-1

`binary_search_with_condition(arr, condition)`

Binary search for the first element that satisfies a condition.

This is useful for finding the boundary where a condition changes from False to True in a sorted array.

Parameters:

Name	Type	Description	Default
`arr`	`List[T]`	Sorted list of elements	required
`condition`	`Callable[[T], bool]`	Function that returns True for desired elements	required

Returns:

Type	Description
`int`	Index of first element satisfying condition, -1 if none found

Examples:

>>> binary_search_with_condition([1, 2, 3, 4, 5], lambda x: x >= 3)
2
>>> binary_search_with_condition([1, 2, 3, 4, 5], lambda x: x > 10)
-1