Binary search is a fast and efficient way to find a target element in a sorted array. Instead of scanning every element one-by-one (like linear search), binary search checks the middle of the array and eliminates half of the elements in each step. This makes the algorithm run in O(log n) time complexity.
How It Works
We start with two pointers:
low
points to the beginning of the array
high
points to the end of the array
We calculate the mid
index using Math.floor((low + high) / 2)
. Then we compare arr[mid]
with the target:
- If
arr[mid]
equals the target, we have found the element and return its index.
- If
arr[mid]
is less than the target, we ignore the left half by setting low = mid + 1
.
- If
arr[mid]
is greater than the target, we ignore the right half by setting high = mid - 1
.
We repeat this until low
becomes greater than high
. If we haven’t returned by then, the target is not in the array, and we return -1
.
Understanding Different Cases
- Target in the array: Binary search finds it quickly and returns the index.
- Target not in the array: The search range shrinks until no possibilities are left, and we return -1.
- Target smaller than all elements: We never find a valid mid and the loop ends quickly with -1.
- Target greater than all elements: Similarly, the algorithm eliminates all elements, and returns -1.
- Empty array: Since there are no elements, the search ends immediately with -1.
- Single element arrays: Either the element matches the target or it doesn’t—easy to handle.
This iterative version avoids the overhead of recursive calls and is suitable for memory-constrained environments or large input sizes.