Binary Search: Binary Search, Efficient Algorithms, Advanced Applications

How Binary Search Works

1. Initial Setup: Start with two pointers, low and high, which represent the bounds of the search interval. Initially, low is set to 0, and high is set to the length of the array minus one.

2. Middle Element: Calculate the middle index mid of the current interval. The middle index is computed as mid = (low + high) // 2.

3. Comparison:

   • If the middle element arr[mid] is the target value, the search is complete, and the index mid is returned.
   • If the target value is less than arr[mid], adjust the high pointer to mid - 1.
   • If the target value is greater than arr[mid], adjust the low pointer to mid + 1.

4. Repeat: Repeat steps 2 and 3 until the low pointer exceeds the high pointer. If the target value is not found, return -1 to indicate that the value is not in the array.

Binary Search Algorithm in Python

Here is the Python implementation of binary search:

python
def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        mid_value = arr[mid]
        
        if mid_value == target:
            return mid  # Target found, return its index
        elif mid_value < target:
            low = mid + 1  # Search in the right half
        else:
            high = mid - 1  # Search in the left half
    
    return -1  # Target not found

# Example usage
sorted_array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 7

result = binary_search(sorted_array, target)
if result != -1:
    print(f"Element {target} found at index {result}")
else:
    print(f"Element {target} not found in the array")

Explanation of the Example

1. Initial State:

   • arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
   • target = 7
   • low = 0, high = 9

2. First Iteration:

   • mid = (0 + 9) // 2 = 4
   • arr[mid] = 9
   • target < arr[mid], so high = mid - 1 = 3

3. Second Iteration:

   • mid = (0 + 3) // 2 = 1
   • arr[mid] = 3
   • target > arr[mid], so low = mid + 1 = 2

4. Third Iteration:

   • mid = (2 + 3) // 2 = 2
   • arr[mid] = 5
   • target > arr[mid], so low = mid + 1 = 3

5. Fourth Iteration:

   • mid = (3 + 3) // 2 = 3
   • arr[mid] = 7
   • arr[mid] == target, target found at index 3

Visual Representation

Imagine the array as follows:

makefile
Index:   0  1  2  3  4  5  6  7  8  9
Array:   1  3  5  7  9  11 13 15 17 19
Target:  7

• Initial bounds: low = 0, high = 9
• After first iteration: mid = 4, high = 3
• After second iteration: mid = 1, low = 2
• After third iteration: mid = 2, low = 3
• After fourth iteration: mid = 3, found target at index 3

Recursive Implementation of Binary Search

Binary search can also be implemented recursively. The recursive approach follows the same logic as the iterative approach but uses function calls to reduce the search range. Here's how you can implement it:

Recursive Binary Search Algorithm in Python

python
def binary_search_recursive(arr, target, low, high):
    if low > high:
        return -1  # Base case: target is not found

    mid = (low + high) // 2
    mid_value = arr[mid]

    if mid_value == target:
        return mid  # Target found, return its index
    elif mid_value < target:
        return binary_search_recursive(arr, target, mid + 1, high)  # Search in the right half
    else:
        return binary_search_recursive(arr, target, low, mid - 1)  # Search in the left half

# Example usage
sorted_array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 7

result = binary_search_recursive(sorted_array, target, 0, len(sorted_array) - 1)
if result != -1:
    print(f"Element {target} found at index {result}")
else:
    print(f"Element {target} not found in the array")

Explanation of the Recursive Example

1. Initial Call: binary_search_recursive(arr, 7, 0, 9)

   • low = 0, high = 9
   • mid = (0 + 9) // 2 = 4
   • arr[mid] = 9
   • target < arr[mid], so call binary_search_recursive(arr, 7, 0, 3)

2. Second Call: binary_search_recursive(arr, 7, 0, 3)

   • low = 0, high = 3
   • mid = (0 + 3) // 2 = 1
   • arr[mid] = 3
   • target > arr[mid], so call binary_search_recursive(arr, 7, 2, 3)

3. Third Call: binary_search_recursive(arr, 7, 2, 3)

   • low = 2, high = 3
   • mid = (2 + 3) // 2 = 2
   • arr[mid] = 5
   • target > arr[mid], so call binary_search_recursive(arr, 7, 3, 3)

4. Fourth Call: binary_search_recursive(arr, 7, 3, 3)

   • low = 3, high = 3
   • mid = (3 + 3) // 2 = 3
   • arr[mid] = 7
   • arr[mid] == target, target found at index 3

Visual Representation for Recursive Approach

The process of narrowing down the search interval in the recursive approach can be visualized similarly to the iterative approach:

1. Initial bounds: low = 0, high = 9
2. After first recursive call: mid = 4, high = 3
3. After second recursive call: mid = 1, low = 2
4. After third recursive call: mid = 2, low = 3
5. After fourth recursive call: mid = 3, found target at index 3

Time Complexity

The time complexity of binary search, both iterative and recursive, is $𝑂(\log 𝑛)$, where $𝑛$ is the number of elements in the array. This efficiency makes binary search suitable for large sorted datasets.

Advantages of Binary Search

• Efficiency: With a time complexity of $𝑂(\log 𝑛)$, binary search is much faster than linear search for large datasets.
• Simplicity: The algorithm is straightforward and easy to implement.
• Deterministic: Binary search always follows the same steps and guarantees finding the target if it exists in the array.

Practical Considerations

• Sorted Array: Binary search requires the array to be sorted. If the array is not sorted, you must sort it first, which takes $𝑂(𝑛\log 𝑛)$ time.
• Non-recursive Approach: In practice, the iterative approach is often preferred over the recursive one because it avoids the overhead of recursive function calls, especially in languages with limited stack size.

Applications of Binary Search

Binary search is a versatile algorithm with numerous applications beyond simply finding an element in an array. Here are some key applications:

1. Finding the Lower/Upper Bound:
   • Lower Bound: The smallest index at which a given value could be inserted to maintain sorted order.
   • Upper Bound: The largest index at which a given value could be inserted to maintain sorted order.
2. Searching in Infinite Lists:
   • Used in situations where the list size is not known, such as in certain streaming data applications.
3. Optimization Problems:
   • Binary search can be used to solve optimization problems where you need to find the minimum or maximum value that satisfies certain conditions.

Example: Finding the Lower Bound

The lower bound of a value in a sorted array is the index of the first element that is not less than the target value. Here’s how you can find the lower bound using binary search:

python
def lower_bound(arr, target):
    low = 0
    high = len(arr)
    
    while low < high:
        mid = (low + high) // 2
        if arr[mid] < target:
            low = mid + 1
        else:
            high = mid
            
    return low

# Example usage
sorted_array = [1, 3, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 3

index = lower_bound(sorted_array, target)
print(f"Lower bound for {target} is at index {index}")

Example: Finding the Upper Bound

The upper bound of a value in a sorted array is the index of the first element that is greater than the target value. Here’s how you can find the upper bound using binary search:

python
def upper_bound(arr, target):
    low = 0
    high = len(arr)
    
    while low < high:
        mid = (low + high) // 2
        if arr[mid] <= target:
            low = mid + 1
        else:
            high = mid
            
    return low

# Example usage
sorted_array = [1, 3, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 3

index = upper_bound(sorted_array, target)
print(f"Upper bound for {target} is at index {index}")

Searching in Infinite Lists

In cases where the list size is unknown or potentially infinite, such as searching for a specific condition in a stream of data, binary search can be adapted. This involves first identifying a range where the target could be and then performing binary search within that range.

python
def find_in_infinite_list(is_target):
    low = 0
    high = 1
    
    # First, find the bounds
    while not is_target(high):
        low = high
        high *= 2
    
    # Now perform binary search within these bounds
    while low <= high:
        mid = (low + high) // 2
        if is_target(mid):
            return mid
        elif not is_target(mid):
            low = mid + 1
        else:
            high = mid - 1
            
    return -1

# Example usage
def is_target(index):
    # Example condition for target: true if index is greater than or equal to 100
    return index >= 100

result = find_in_infinite_list(is_target)
print(f"Target found at index {result}")

Binary Search in Practice

In real-world applications, binary search is often used in conjunction with other algorithms and data structures. Here are a few examples:

• Databases: Indexes in databases are often implemented using binary search on sorted keys for quick lookup.
• Libraries: Many programming libraries provide binary search functions for common tasks, such as searching in sorted lists or arrays.
• Competitive Programming: Binary search is frequently used in competitive programming problems, particularly in scenarios involving range queries or finding optimal solutions efficiently.

Binary Search in Libraries and Frameworks

Many programming languages and libraries provide built-in functions to perform binary search, making it easier for developers to implement this algorithm efficiently without having to write it from scratch. Here are some examples:

Python: bisect Module

Python’s bisect module provides functions for binary search operations on sorted lists:

1. bisect_left: Finds the insertion point for a value in a sorted list to maintain order (i.e., the lower bound).

2. bisect_right: Finds the insertion point for a value in a sorted list to maintain order, but returns the position to the right of any existing entries of the target (i.e., the upper bound).

Here’s how to use these functions:

python
import bisect

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

# Finding the lower bound
lower_bound_index = bisect.bisect_left(sorted_array, target)
print(f"Lower bound for {target} is at index {lower_bound_index}")

# Finding the upper bound
upper_bound_index = bisect.bisect_right(sorted_array, target)
print(f"Upper bound for {target} is at index {upper_bound_index}")

C++: std::lower_bound and std::upper_bound

In C++, the <algorithm> library provides std::lower_bound and std::upper_bound for binary search operations:

cpp
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> sorted_array = {1, 3, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int target = 3;

    // Finding the lower bound
    auto lower = std::lower_bound(sorted_array.begin(), sorted_array.end(), target);
    std::cout << "Lower bound for " << target << " is at index " << (lower - sorted_array.begin()) << std::endl;

    // Finding the upper bound
    auto upper = std::upper_bound(sorted_array.begin(), sorted_array.end(), target);
    std::cout << "Upper bound for " << target << " is at index " << (upper - sorted_array.begin()) << std::endl;

    return 0;
}

Java: Collections.binarySearch

Java provides a binarySearch method in the Collections class for performing binary search on lists:

java
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class BinarySearchExample {
    public static void main(String[] args) {
        List<Integer> sortedList = Arrays.asList(1, 3, 3, 5, 7, 9, 11, 13, 15, 17, 19);
        int target = 7;

        // Performing binary search
        int index = Collections.binarySearch(sortedList, target);
        if (index >= 0) {
            System.out.println("Element " + target + " found at index " + index);
        } else {
            System.out.println("Element " + target + " not found in the list");
        }
    }
}

Common Mistakes and How to Avoid Them

1. Assuming the Array is Sorted:

   • Mistake: Applying binary search to an unsorted array.
   • Solution: Ensure the array is sorted before performing binary search. If not, sort it using a sorting algorithm or library function.

2. Incorrect Calculation of mid:

   • Mistake: Miscomputing the middle index, which can lead to incorrect results or infinite loops.
   • Solution: Use mid = (low + high) // 2 in languages like Python. In languages prone to overflow (e.g., C++ or Java), use mid = low + (high - low) / 2.

3. Not Handling Edge Cases:

   • Mistake: Failing to handle edge cases such as empty arrays or arrays with one element.
   • Solution: Explicitly check for these conditions before proceeding with the binary search.

4. Infinite Loops:

• Mistake: Incorrectly updating the low and high pointers, leading to infinite loops.
• Solution: Ensure the pointers are correctly adjusted in each iteration. For example, use low = mid + 1 when searching the right half and high = mid - 1 when searching the left half.

Like

Share

# Tags