Binary search for 54 in sorted data

Binary search finds a key in a sorted array by repeatedly comparing it with the middle element and discarding the half that cannot contain it.

Algorithm

BINARYSEARCH(a, n, key)
1. low = 0, high = n - 1
2. while low <= high
3.     mid = (low + high) / 2
4.     if key == a[mid]  return mid        // found
5.     else if key < a[mid]  high = mid - 1  // search left half
6.     else  low = mid + 1                 // search right half
7. return -1                               // not found

int binarySearch(int a[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (a[mid] == key) return mid;
        else if (key < a[mid]) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

Search 54 in 8, 15, 36, 40, 41, 54, 62 (index 0 to 6)

Answer: 54 is found at index 5 (position 6) in 2 comparison steps.