Recursive binary search

Easy TimeO(log n) SpaceO(log n) stack

Given an array arr sorted in ascending order, a target, and the low and high bounds of the region still being searched, return the target's index or -1. The bounds are inclusive, so a low above high is an empty region and means the target is absent.

Examples

Example 1

Input
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25]target = 23low = 0high = 12
Output
11
Thirteen odd values, and 23 is the twelfth of them — index 11.

Example 2

Input
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25]target = 4low = 0high = 12
Output
-1
Every value here is odd, so 4 is absent.

The Code

function binarySearch(arr, target, low, high) {
  if (low > high) return -1;
  const mid = Math.floor((low + high) / 2);
  if (arr[mid] === target) return mid;
  if (arr[mid] < target) return binarySearch(arr, target, mid + 1, high);
  return binarySearch(arr, target, low, mid - 1);
}
binarySearch([1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25], 23, 0, 12);
Done
Step through binarySearch([1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25], 23, 0, 12) call by call

More like this

All searching examples (8) →