SimuVedaAlgorithms Lab Open in the lab

Searching / Beginner

Binary Search Visualizer

On a sorted array, look at the middle value. If it is too small, throw away the left half. If too big, throw away the right half.

Start the Binary Search simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(1)
Average timeO(log n)
Worst timeO(log n)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Binary search needs sorted values, so the input is sorted first. Search for 63. [3, 8, 15, 23, 42, 51, 63, 77, 90]
  2. The middle of [0..8] is index 4, value 42.
  3. 42 < 63, so the target can only be on the right. Move lo to 5.
  4. The middle of [5..8] is index 6, value 63.
  5. 63 equals 63. Found at index 6 with only 2 checks.

Try it with your own input →

Binary search in Java, Python, C++, C and JavaScript

int binarySearch(int[] a, int target) {
  int lo = 0, hi = a.length - 1;
  while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == target) return mid;
    if (a[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}
def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
int binarySearch(const vector<int>& a, int target) {
  int lo = 0, hi = (int)a.size() - 1;
  while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == target) return mid;
    if (a[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}
int binarySearch(int a[], int n, int target) {
  int lo = 0, hi = n - 1;
  while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == target) return mid;
    if (a[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}
function binarySearch(a, target) {
  let lo = 0, hi = a.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (a[mid] === target) return mid;
    if (a[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

In an interview

In Java, write mid as lo + (hi − lo) / 2. Writing (lo + hi) / 2 can overflow for very large arrays.

More searching