ACAlgoGeeks

1left = 0, right = 7   (n = 8)
2while left <= right:
3  mid = (left + right) / 2   → mid = 3
4  if arr[mid] == target: return mid   ✓
5  if arr[mid] < target: left = mid + 1
6  else: right = mid - 1
7return -1

1function binarySearch(arr: number[], target: number): number {
2  let left = 0, right = arr.length - 1;
3  while (left <= right) {
4    const mid = Math.floor((left + right) / 2);
5    if (arr[mid] === target) return mid;
6    if (arr[mid] < target) left = mid + 1;
7    else right = mid - 1;
8  }
9  return -1;
10}

About

Binary search finds the position of a target value in a sorted array by repeatedly comparing the target with the middle element and narrowing the search range to the left or right half.

Step-by-step explanation

Step 1 — Initialization: Set left = 0 and right = n - 1 so the search range is the entire sorted array. The invariant is: if the target exists, it lies in the range [left, right].

Step 2 — Loop: While left <= right, compute the middle index mid = floor((left + right) / 2). This splits the range in half. Compare the element at mid with the target.

Step 3 — Comparison: If arr[mid] equals the target, we have found it; return mid. If arr[mid] is less than the target, the target must be in the right half (all elements left of mid are smaller), so set left = mid + 1. Otherwise arr[mid] is greater, so the target is in the left half; set right = mid - 1.

Step 4 — Termination: If the loop exits without returning, left > right, meaning the range is empty and the target is not in the array; return -1. Each step halves the search space, so the algorithm runs in O(log n) time and O(1) extra space.

What's happening

arr[mid]=7 == target → found at 3.

Time Complexity

O(log n)

Space Complexity

O(1)

Output

arr[mid]=7 == target → found at 3.