Iterative Binary Search

The binary search algorithm is easily implemented in both an iterative and recursive function. We’ll look at both versions and see how they compare.

The pseudocode for an iterative version of binary search is shown below.

 1function BINARYSEARCH(ARRAY, VALUE)
 2    START = 0
 3    END = size of ARRAY - 1
 4    loop while START <= END
 5        MIDDLE = INT((START + END) / 2)
 6        if ARRAY[MIDDLE] == VALUE then
 7            return MIDDLE
 8        else if ARRAY[MIDDLE] > VALUE then
 9            END = MIDDLE – 1
10        else if ARRAY[MIDDLE] < VALUE then
11            START = MIDDLE + 1
12        end if
13    end loop
14    return -1
15end function

This function starts by setting the initial values of start and end on lines 2 and 3 to the first and last indexes in the array, respectively. Then, the loop starting on line 4 will repeat while the start index is less than or equal to the end index. If we reach an instance where start is greater than end, then we have searched the entire array and haven’t found our desired value. At that point the loop will end and we will return -1 on line 14.

Inside of the loop, we first calculate the middle index on line 5. Then on line 6 we check to see if the middle element is our desired value. If so, we should just return the middle index and stop. It is important to note that this function will return the index to an instance of value in the array, but it may not be the first instance. If we wanted to find the first instance, we’d add a loop at line 7 to move forward in the array until we were sure we were at the first instance of value before returning.

If we didn’t find our element, then the if statements on lines 8 and 10 determine which half of the array we should look at. Those statements update either end or start as needed, and then the loop repeats.