Understanding Binary Search (Bisection) in Python

Binary search, also known as the bisection method, is a fundamental algorithm used to find the position of a target value within a sorted array. It operates by repeatedly dividing the array in half and eliminates one half from consideration until the target value is found. This makes it a powerful and efficient search mechanism with a time complexity of $O(\log n)$.

How Binary Search Works

Binary search operates under two critical assumptions:

1. Array must be sorted: Binary search can only be applied to data structures that are sorted.
2. Divide and conquer: By selecting the middle element as the pivot, the algorithm determines if the target lies to the left or right of the pivot, effectively halving the search space.

Algorithm Steps

1. Initialize two pointers, `left` and `right`, representing the bounds of the array.
2. Calculate the middle index: `mid = left + (right - left) // 2`.
3. Compare the middle element of the array with the target:
   • If equal, return the middle index.
   • If the target is less than the middle element, adjust the `right` pointer to `mid - 1`.
   • If the target is greater, adjust the `left` pointer to `mid + 1`.
4. Repeat steps 2-3 until the `left` pointer exceeds the `right` pointer.
5. If the target isn't found, return a value indicating failure (commonly `-1`).

Python Implementation

Here's a simple implementation of binary search in Python:

• Efficiency: With its logarithmic time complexity, binary search is significantly faster than linear search techniques.
• Scalability: Works well with large datasets.
• Lower Bound Binary Search: Used to find the smallest index at which a given element can be inserted.
• Upper Bound Binary Search: Finds the largest index at which a given element can be inserted.
• Introduction to Algorithms, Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C.
• The Algorithm Design Manual, Skiena, S.