In-Depth Look at Binary Search

Set up the start and end points of the search range.

Copy
def binary_search(arr, target):
    start, end = 0, len(arr) - 1

Check the middle element and halve the search range.

Copy
while start <= end:
    mid = (start + end) // 2  # midpoint
    if arr[mid] == target:  # found the target
        return mid
    elif arr[mid] < target:  # target is larger than the midpoint value
        start = mid + 1
    else:  # target is smaller than the midpoint value
        end = mid - 1

return -1  # not found

1. Worst-Case Time Complexity: O(log n)

   • In binary search, the search range is halved at each step. Thus, with n elements, it requires at most log n steps.

2. Best-Case Time Complexity: O(1)

   • If the target element is located at the midpoint, it can be found in the first comparison.

3. Average Time Complexity: O(log n)

   • In most cases, binary search operates with logarithmic time complexity, as the search range is halved at each step in the search process.