Binary search

Question 1

Describe the steps of a binary search.

Answer 1

• Find the midpoint of the list
• If midpoint is equal to search item, search item is found
• If search item is greater than the midpoint, search second half of list.
• This is repeated until the midpoint is equal to the search item.

Question 2

Write a binary search in pseudocode.

Answer 2

array myIntegers[5]
start = 0
end = 4
found = false
input searchItem(“”)
midpoint = 0
while (found == false AND start <= end)
midpoint = (start + end) DIV 2
if (myIntegers[midpoint] == searchItem) then
found = true
elseif (myIntegers[midpoint] > searchItem)
end = midpoint - 1
else
start = midpoint + 1
endif
endwhile

Question 3

Compare a linear search and a binary search

Answer 3

• Both work on strings using the ASCII code value
• Binary search can only be used on sorted data, linear search items do not have to be sorted
• Linear might be quicker than binary if the search item is at the start of the list
• If a value is duplicated in the items to be searched, only the first one to be found is returned