What is Binary Search?

Binary search is a more efficient way of searching through an array that only works on sorted arrays. The ideology is as follows:

1. Start by checking the midpoint of the array.
   1. If the midpoint value matches the value you're searching for, then return that index.
   2. If the midpoint value is greater than the value you're searching for, refine the search by:
      1. Only searching through the bottom half (if the array is descending).
      2. Only searching through the top half (if the array is ascending).
   3. If the midpoint value is smaller than the value you're searching for, refine the search by:
      1. Only searching through the bottom half (if the array is ascending).
      2. Only searching through the top half (if the array is descending).

When you perform these searches, you want to exclude the value you've already compared. To do this, you should always set the lower or upper bound to middle - 1 or middle + 1 respectively. So, for an array $1,3,4,7,9$ and a searchable item $3$:

1. First perform binary search to compare $4$ to $3$.
2. This narrows down the possible numbers to compare to $1,3$, as we exclude $4$, since we've already compared it.
3. Thus, we perform binary search again on $1,3$.

Binary Search Implementation: Iterative

Return the index of an integer array where the value matches the value that you are searching for. The array is in ascending order.

#include <stdio.h>

int binarySearch(int list[], int listLength, int item) {
  int low = 0;
  int high = listLength - 1;
  int middle;

  while (low <= high) {
    middle = (low + high) / 2;
    if (item == list[middle])
      return middle;
    else if (item < list[middle])
      high = middle - 1;
    else
      low = middle + 1;
  }
  return -1;
}

int main() {
  int list[] = {1, 3, 5, 7, 9, 10, 12};
  printf("Found 9 at index %d\n", binarySearch(list, 7, 9));
  return 0;
}

Binary Search Implementation: Recursive

You can do the same search as above by using recursion.

#include <stdio.h>

int binarySearchHelper(int list[], int listLength, int item, int low, int high) {
	// recursive function
	int middle = (low + high) / 2;
	if (low <= high) {
		if (item == list[middle]) {
			return middle;
		} else if (item < list[middle]) {
			return binarySearchHelper(list, listLength, item, low, middle - 1);
		} else if (item > list[middle]) {
			return binarySearchHelper(list, listLength, item, middle - 1, high);
		}
	} else {
		return -1;
	}
}

int binarySearch(int list[], int listLength, int item) {
  return binarySearchHelper(list, listLength, item, 0, listLength - 1);
}

int main() {
  int list[] = {1, 3, 5, 7, 9, 10, 12};
  printf("Found 9 at index %d\n", binarySearch(list, 7, 9));
  return 0;
}