Next to linear search, binary search is arguably the simplest to implement among the many search algorithms. Binary search can be summarized with the following rules:

- The list in which we are performing the search should be sorted beforehand.
- If the value being searched is less than the value in the middle of the list, then search only on the left side of the list.
- Otherwise, search only on the right side of the list.
- The value being searched is always in the middle.

Rules 2 and 3 give a hint as to why binary search is referred to as “divide and conquer search”. Basically, we “divide” the list into two, and “conquer” (i.e., perform the search on) one side. We keep performing this “divide-and-conquer” concept either **iteratively** or **recursively**, until we find the value we are looking for or until we’ve exhausted the search.

For example, in this list, we’re looking for the value **23**.

The search would look like the following:

#### Method #1: Iterative Binary Search

The more common way of implementing binary search is through a loop which iterates through sections of the list.

We first define a function that accepts the list *arr* and the value we are searching for *val*. For this, we’ll assume that the values in *arr* are already sorted. We’ll initialize variables *first* and *last*, which are pointers to the lower bound and the upper bound of the list, respectively. We’ll be updating these variables as we search through the list.

def iterativeBinarySearch(arr, val): first = 0 last = len(arr) - 1

Next, we’ll look for middle point between first and last. This can be calculated as the following (note that double slash means integer division):

mid = (first + last) // 2

If the value in the middle matches the value we are looking for, then we can return the value of mid and that would be our answer. Otherwise, we’ll need to update value of first or last, depending on how the value we are looking for compares with the value in the middle of the search space. For example, if the value we are looking for is less than the value in the middle, then we change *last* with mid – 1, which will then limit our search space to only the left side of the list. If the value is more than the value in the middle, then we change the *first* variable with mid + 1, which will limit our search space to only the right side of the list. This logic is defined in the outer else statement of the code:

if arr[mid] == val: return mid elif val < arr[mid]: last = mid - 1 elif val > arr[mid]: first = mid + 1

Now that we have implemented all of the rules of binary search in our code, we can then put them all together and use a while loop to iteratively update the *first* and *last* variables until there are no more elements to look at. We know whether there are logically no more elements to search if the value of *first *exceeds the value of *last*. Once we’ve passed that condition, then the function will return -1, meaning that the value was not found.

def iterativeBinarySearch(arr, val): first = 0 last = len(arr) - 1 while (first <= last): mid = (first + last) // 2 if arr[mid] == val: return mid elif val < arr[mid]: last = mid - 1 elif val > arr[mid]: first = mid + 1 return -1

#### Method #2: Recursive Binary Search

Once we’ve grasped the rules of binary search, it’s quite simple to modify the iterative approach into a recursive one. We know that the terminating condition of binary search is if the value of the supposed lower bound *first* exceeds the value of the supposed upper bound *last*. So, we can already define that in our recursive function:

def recursiveBinarySearch(arr, val, first, last): if first > last: return -1

The rest of the function will then look almost the same as the iterative approach, with the only difference that we recursively call the function along with the updates to *first* and *last* when we’ve met the conditions.

if arr[mid] == val: return mid elif val < arr[mid]: return binarySearch(arr, val, first, mid-1) elif val > arr[mid]: return binarySearch(arr, val, mid+1, last)

Putting it all together, the recursive binary search would look like this:

def recursiveBinarySearch(arr, val, first, last): if first > last: return -1 else: mid = (first + last) // 2 if arr[mid] == val: return mid elif val < arr[mid]: return recursiveBinarySearch(arr, val, first, mid-1) elif val > arr[mid]: return recursiveBinarySearch(arr, val, mid+1, last)

For more code on different search algorithms, check out my notebook on Github.