Binary search (or half interval search) algorithm is a searching method used only in sorted arrays. It relies on divide and conquer strategy to accomplish its purpose. In every search iteration, half of the elements of the array are eliminated as possible solutions. Binary search is very efficient for large arrays. Its performance makes it ideal when resorting is not required.

In each iteration, the algorithm:

1. Compares the search value with the value of the middle element of the array.

• If the values match, then the value was found.

• If the search value is less than the middle element of the array, then the algorithm repeats its action on the sub-array to the left of the middle element.

• If the search value is greater than the middle element of the array, then the algorithm repeats its action on the sub-array to the right of the middle element.

2. If the remaining array to be searched is empty, then the value was not found.

See inside

Algorithm Analysis / Time Efficiency

Assume n represents the size of a list to be searched.

The Binary Search has the following time efficiency:

• • Best Case: the key is found on the first try.

  • Worst Case: the key is not in the list or is at either end of a sublist. Here the n elements must be divided by 2 until there is just one element, and then the last element must be tested. This equals 1 + log2n comparisons. Thus, in the worst case, the algorithm is log2n. For example, if the size of the list is 8, then the number of comparisons needed is 3 since log28 = 3.

Extra: mathematical explanation

• • • For list sizes that are not powers of 2 you can round n up to the next power of 2 and take the exponent. For example, if the size of an array is 9. Since 9 is not a power of 2 round 9 up to 16 (the next power of 2), which equals 24. Therefore you would need four comparisons to find it.

  • Average Case: you would need about half the comparisons of the worst case. 

Tasks

1. Download p211 Pseudocode example 20: Binary search and test it in Mr Mulkey's p-code tool.

2. Write example 20 in Python using codeskulptor.

3. From the EZ Pseudocode program load Binary_Search and compare it with example 20.    example 20 

4. Read through Interactivepython - The binary search. Step through the code using codeLens and try the self-check.

5. Read and try - Binary v linear comparison visualisation

Assignment

Binary search exercise