Binary search |
Binary search is a more efficent searching algorithim than serial search. It does have one major draw back which is that the list must be ordered before it can work. It is known as a divide and conquer problem as it will keep splitting the problem in half until it has arrived at a solution.
It will first of all find the mid point of the list and compare the search term against it. If the search term is bigger then it will only look at the top half of the list. Otherwise it will look at the bottom half. If they are the same then it has found the item! It will then keep splitting the list until it has found the item or the list can not be split anymore.
The psuedo code below explains how binary search works.
Inputs - A ordered list, search item
Output - If the value is found
- Start = 1
- End = List.length()
- found = FALSE
- WHILE (end - start) >= 2
- mid = ((end - start) / 2) + start
- IF list[mid] = search THEN
- found = TRUE
- start = end
- ELSE IF list[mid] < search
- end = mid
- else
- start = mid
- END WHILE
- print "was it found " + found