Section 7.2
7 Standard Algorithms
7.2 Binary Search
A binary search cab be performed on an array of sequential data items.
If the middle item matches the search item then we have found the item and
we can stop the search.
Else if the middle item is greater then the search item, then only the first half
the table needs to be searched.
Else if the middle item is less than the search item then only the second half
of the table needs to be searched.
We repeat this process until:
- we find the search item
- when we get to one item which is not equal to the search item
Pseudocode
'Intialise
MatchFlag = 0
SearchFail = 0
DIM array
READ data items into array
INPUT SearchValue
Calculate startp and endp
DO
Calculate midp
IF SearchValue found THEN
MatchFlag = 0
ELSEIF startp = endp THEN
SearchFail = 1
ELSEIF middle > searchitem THEN
endp = midp
ELSE show error
LOOP UNTIL MatchFlag = 1 OR SearchFlag = 1
'Output
Show Output
