🤖

DSA Assistant

Hi! I'm your DSA Guide. Today we are searching for target element 23 in a sorted array. Binary Search works by dividing search bounds in half!

Target: 23Left: 0 | Mid: 4 | Right: 8
2
[0]
5
[1]
8
[2]
12
[3]
16
[4]
23
[5]
38
[6]
56
[7]
72
[8]
Step 1 of 4

Algorithm Code

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid  # Found target!
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Mini Check Task

What is the worst-case number of comparisons to search in an array of 8 elements using Binary Search?

Understanding Binary Search: Theory & Mathematical Complexity

Binary search is an efficient divide-and-conquer algorithm used to find the position of a target value within a sorted array. Unlike linear search which examines every element sequentially, binary search repeatedly halves the search space.

Mathematical Time Complexity Derivation

Suppose an array has size $N$. After 1 step, the remaining elements are $N / 2$. After 2 steps, $N / 4$, and after $k$ steps, the search space reduces to $N / 2^k$. The algorithm terminates when the search space reduces to 1 element:

N / 2^k = 1 ==> 2^k = N ==> k = log2(N)
  • Best-Case Time Complexity: $O(1)$ when the target is at the initial midpoint.
  • Worst-Case Time Complexity: $O(\log n)$ when target is at the boundary or missing.
  • Auxiliary Space Complexity: $O(1)$ iterative memory space.