Binary search
Another example of a computer searching algorithmA sequence of logical instructions for carrying out a task. In computing, algorithms are needed to design computer programs. is binary search. This is a more complex algorithm than linear searchAn algorithm designed to search for the presence of an item stored within an array (list). and requires all items to be in order.
With each loopThe repetition of an activity within a computer program. that is run, half of the dataUnits of information. In computing there can be different data types, including integers, characters and Boolean. Data is often acted on by instructions. is removed from the search. To do this, the algorithm uses the indexThe position of a piece of data in a list. of items in the list - an index is the number given to the position of an item in a list.
To determine the next item to be checked in a list, the midpoint has to be identified. This is found by adding the lowest index to the highest index and dividing by two, then rounding either up or down to the nearest integerA whole number - this is one data type used to define numbers in a computer program. Integers can be unsigned (represent positive numbers) or signed (represent negative or positive numbers). if needed. Whether we round up or down does not matter, as long as within a particular search the same method is applied. For example, if the highest index in a list is 8 and the lowest is 0, the midpoint can be found using the following sum:
Highest index (8) + lowest index (0) = 8
8/2 = 4
The algorithm runs as follows:
- Start by setting the counter to the middle position in the list.
- If the value held there is a match, the search ends.
- If the value at the midpoint is less than the value to be found, the list is divided in half, the lower half of the list is ignored and the search keeps to the upper half of the list.
- Otherwise, if the value at the midpoint is greater than the value to be found, the upper half of the list is ignored and the search keeps to the lower half of the list.
- The search moves to the midpoint of the remaining items. Steps 2 through 4 continue until a match is made or there are no more items to be found.
Binary search example
This algorithm could be used to search the following list for the number 7:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
In a trace tableUsed when testing a program to record changes in variable values as code executes., this would look like:
| Search term | Start | End | Mid | Found | List |
| 7 | 1 | 10 | 5 | False | [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] |
| 6 | 10 | 8 | False | [6, 7, 8, 9, 10] | |
| 6 | 7 | 6 | False | [6, 7] | |
| 7 | 7 | 7 | True | [7] |
| Search term | 7 |
|---|---|
| Start | 1 |
| End | 10 |
| Mid | 5 |
| Found | False |
| List | [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] |
| Search term | |
|---|---|
| Start | 6 |
| End | 10 |
| Mid | 8 |
| Found | False |
| List | [6, 7, 8, 9, 10] |
| Search term | |
|---|---|
| Start | 6 |
| End | 7 |
| Mid | 6 |
| Found | False |
| List | [6, 7] |
| Search term | |
|---|---|
| Start | 7 |
| End | 7 |
| Mid | 7 |
| Found | True |
| List | [7] |
In pseudocode Also written as pseudo-code. A method of writing up a set of instructions for a computer program using plain English. This is a good way of planning a program before coding., this would look like:
Find <-- 7
Found <-- False
Start <-- 0
End <-- length(list) WHILE Found = False AND Start <= End Mid <-- (Start + End) DIV 2 IF list[Mid] = Find THEN OUTPUT 'Found at' + Mid Found <-- True ELSE IF List[Mid] > Find THEN End <-- Mid - 1 ELSE Start <-- Mid + 1 ENDIF ENDIF
ENDWHILE IF Found = False THEN OUTPUT 'Not found'
ENDIFSearching a data set using binary search
