Binary Search

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one.

How Binary Search Works

Sorted List: Start with a sorted list of items.
Find the Middle Element: Find the middle element of the list.
Compare the Target: Compare the target value with the middle element.
Narrow Down the Search Space: If the target value is less than the middle element, repeat the process with the left half of the list. If the target value is greater than the middle element, repeat the process with the right half of the list.
Repeat Until Found: Repeat steps 2-4 until the target value is found or the search space is empty.

Example Use Cases

Finding an Element in a Sorted Array: Binary search is particularly useful for finding an element in a large sorted array.
Autocomplete and Suggestion Systems: Binary search can be used to quickly find matching suggestions in a sorted list of words or phrases.

Example Code (Python)

def binary_search(arr, target):
    low, high = 0, len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1  # Return -1 if the target is not found

# Example usage:
arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23
index = binary_search(arr, target)

if index != -1:
    print(f"Target {target} found at index {index}.")
else:
    print(f"Target {target} not found in the array.")

Time and Space Complexity

Time Complexity: The time complexity of binary search is $$O(\log n)$$, where $$n$$ is the number of elements in the list.
Space Complexity: The space complexity of binary search is $$O(1)$$, as it only requires a constant amount of additional space.

Advantages and Disadvantages

Advantages

Efficient Search: Binary search is much faster than Linear Search for large lists.
Optimized for Sorted Lists: Binary search takes advantage of the fact that the list is sorted.

Disadvantages

Requires Sorted List: Binary search requires the list to be sorted, which can be a disadvantage if the list is not already sorted.
Not Suitable for Small Lists: Binary search may not be the best choice for small lists, as the overhead of the algorithm can be greater than the benefit.

Comparison with Other Search Algorithms

Binary search is often compared to other common search methods, each with its own trade-offs regarding time and space complexity.

AlgorithmTime ComplexitySpace ComplexityBinary Search$$O(\log n)$$$$O(1)$$Linear Search$$O(n)$$$$O(1)$$Hashing$$O(1)$$$$O(n)$$

Real-World Applications

Database Indexing: Binary search is used in database indexing to quickly locate specific data.
File System Search: Binary search can be used to quickly find files in a file system.
Web Search Engines: Binary search is used in web search engines to quickly retrieve relevant search results.