Binary Search

Binary search is an efficient algorithm that searches a sorted list for a desired, or target, element. For example, given a sorted list of test scores, if a teacher wants to determine if anyone in the class scored \(80\), she could perform a binary search on the list to find an answer quickly. Binary search works by halving the number of elements to look through and hones in on the desired value. Binary search can determine if and where an element exists in a list, or determine if it is not in the list at all.

A gif showing a binary search for the number 47 in the given list.

Binary search works by comparing the target value to the middle element of the array. If the target value is greater than the middle element, the left half of the list is eliminated from the search space, and the search continues in the right half. If the target value is less than the middle value, the right half is eliminated from the search space, and the search continues in the left half. This process is repeated until the middle element is equal to the target value, or if the algorithm returns that the element is not in the list at all.

Binary search looks through a sorted list to see if a desired element is in the list. It does this efficiently by halving the search space during each iteration of the program. Basically, binary search finds the middle of the list, asks “is the element I’m looking for larger or smaller than this?” Then it cuts the search space in the list in half and searches only in the left list if the element is smaller, and searches only in the right list if the element is bigger. It repeats this process until it finds the element it is looking for (or reports back that the element isn’t in the list at all). The algorithm uses a divide and conquer (or divide and reduce) approach to search.

Visualization of the binary search algorithm where 4 is the target value.^[1]

In simple terms, the algorithm works as follows:

The following assumes zero indexing, meaning that the left-most element of a list is the \(0^\text{th}\) element.

1. Determine the middle element of a sorted list by taking the value of the floor of \(\frac{\text{low + high}}{2}\), where low is the lowest index of the list, and high is the highest index in the list. So in the list \([1,2,3,4]\), \(2\) (since 2 occurs at index 1) would be the middle. In the list \([1,2,3,4,5]\), \(3\) (since 3 occurs at index 2) is the middle.

2. Compare the value of that middle element with the target value.

3. If the target value is equal to the middle element, return that it is true the element is in the list (if the position of the element in the list is desired, return the index as well).

4. If the target value is less than the middle element, eliminate all elements to the right of (and including) the middle element from the search, and return to step one with this smaller search space.

5. If the target value is greater than the middle element, eliminate all the elements to the left of (and including) the middle element from the search, and return to step one with this smaller search space.

A limitation of binary search is that it can only search in a pre-sorted list. If the list is not pre-sorted, binary search will not work. Linear search may be a better choice of search algorithm for an unsorted list.

Show the steps that binary search would perform to determine if \(14\) is in the following list: \(A =[0,2,5,5,9,10,11,12,14,15]\). Round down when determining the middle element.

---

We have

List	Middle element
\([0,2,5,5,9,10,11,12,14,15]\)	9
\([10,11,12,14,15]\)	12
\([14,15]\)	14

Since, in the third step, the middle element is equal to the target value, we can return that the element is in the list. \(_\square\)

Binary search can be implemented either iteratively or recursively.

Here is an iterative implementation in Python.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def it_binarySearch(mylist, target):
        first = 0
        last = len(mylist)-1

        while first<=last:
            #note: Use of // indicates floor division. Ex. 5//2 = 2
            midpoint = (first + last)//2
            if mylist[midpoint] == target:
                return midpoint
            else:
                if target < mylist[midpoint]:
                    last = midpoint-1
                else:
                    first = midpoint+1

        return None

test_list = [0,3,4,7,9,11,34,46,57,65]
print(it_binarySearch(test_list, 4))
print(it_binarySearch(test_list, 30))
print(it_binarySearch(test_list, 57))

^[2]

Here is a recursive implementation of binary search in Python.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def binary_search_recursive(listOfInts, elem, start=0, end=None):
    if end is None:
        end = len(listOfInts) - 1
    if start > end:
        return 'Value not found in list'

    mid = (start + end) // 2
    if elem == listOfInts[mid]:
        return mid
    if elem < listOfInts[mid]:
        return binary_search_recursive(listOfInts, elem, start, mid-1)
    # elem > listOfInts[mid]
    return binary_search_recursive(listOfInts, elem, mid+1, end)

listOfInts = [0,1,2,3,4,5,22,33,45]

print (binary_search_recursive(listOfInts, 22))

^[3]

Binary search has a worst-case and average-case running time of \(O(\log n)\), making \(O(\log n)\) comparisons, where \(n\) is the number of elements in the array. The worst case occurs when a given target element is not in the list at all. This means the algorithm has halved the list again and again until it reaches a list of size one. To get a list of size \(n\) down to a list of \(1\) element, \(\log n\) divisions must be made. Each step of the binary search halves the search space.

Binary search has a \(O(1)\) best case running time. This occurs when the first midpoint selected is the target value.

Binary search is a key idea in binary search trees which are very important data structures in computer science.

Binary search can be used to help estimate the square roots of numbers. With a few modifications to the basic algorithm shown in the implementation section, Newton's method can be implemented.

How could you use binary search to help you estimate the square root of a number?

---

For a number \(x\), we know that the square root of \(x\) cannot be larger than \(x\). Our initial search space is \([0,x]\). In other words, the "list" is the set of numbers between \(0\) and \(x\).

The basic idea of binary search is to halve the search space with each iteration. What might this look like in the case of square roots? We can select our midpoint the same way we did in the algorithm described in the above sections.

If the midpoint (proposed root) is not equal to \(x\), to determine if we should search to the left of the midpoint or to the right, compare the value of the midpoint squared to the value of \(x\). If \((\text{midpoint})^2\) is less than \(x\), search in the right half of the list; if \((\text{midpoint})^2\) is greater than \(x\), search in the left half of the list.

To calculate the "first" and "last" (or start index of the search space and end index of the search space), if \((\text{midpoint})^2\) is less than \(x\), "first" becomes the current midpoint value, the new midpoint becomes \(\frac{\text{first + last}}{2}\), and the current value of "last" remains the value of "last". If \((\text{midpoint})^2\) is greater than \(x\), the current midpoint value becomes the new "last", the current value of "first" remains the value of "first", and the new midpoint becomes \(\frac{\text{first + last}}{2}\).

Repeat this process until the root is found. \(_\square\)

Below is a Python implementation of the process described above. ^[4]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def sqrt(n, precision=10e-8):
  first, last = 0.0, max(n, 1.0)
  prev, mid = 0, (first + last) / 2.0
  while abs(mid - prev) > precision:
    if mid ** 2 > n:
      last = mid
    else:
      first = mid
    prev, mid = mid, (first + last) / 2.0
  return mid

print sqrt(64) 
print sqrt(5) 

• Divide and Conquer

• Newton's Method

• Root Approximation - Bisection

1. , T. Binary search into array. Retrieved May 2, 2016, from https://en.wikipedia.org/wiki/File:Binary_search_into_array.png
2. , . The Binary Search. Retrieved April 30, 2016, from http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBinarySearch.html
3. , . The Binary Search. Retrieved June 5, 2016, from http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBinarySearch.html
4. Krenzel , S. Deriving Newton's Method from Binary Search. Retrieved May 2, 2016, from http://stevekrenzel.com/articles/newtons-law