Skip to main content
Practice

In-Depth Look at Binary Search

1. Initial Range Setup​

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

Initial Range Setup
def binary_search(arr, target):
    start, end = 0, len(arr) - 1

2. Iterative Comparison and Range Adjustment​

Check the middle element and halve the search range.

Iterative Comparison and Range Adjustment
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

Time Complexity​

  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.

Want to learn more?

Join CodeFriends Plus membership or enroll in a course to start your journey.