When a list is ordered, there is a much better searching strategy Let us take for the example of card picking game I pick a number between 1 and 100, and you try to guess what it is. Each time you guess, I will tell you if your guess is correct, too high, or too low. What is your strategy?
If you play this game with a very young child, they might well adopt a strategy of simply guessing numbers at random. An older child might employ a systematic approach corresponding to linear search, guessing 1; 2; 3; 4; : : : until the mystery value is found.
Of course, virtually any adult will guess 50. If told that the number is higher, then the range of possible values is 50.100. The next logical guess is 75. Each time we guess the middle of the remaining numbers to try to narrow down the possible range. This strategy is called a binary search. Binary means two, and at each step, we are dividing the remaining numbers into two parts.
We can employ a binary search strategy to look through a sorted list. The basic idea is that we use two variables to keep track of the endpoints of the range in the list where the item could be. Initially, the target could be anywhere in the list, so we start with variables low and high set to and last positions of the list, respectively.
The heart of the algorithm is a loop that looks at the item in the middle of the remaining range to compare it to x. If x is smaller than the middle item, then we move top, so that the search is narrowed to the lower half. If x is larger, then we move low, and the search is narrowed to the upper half. The loop terminates when x is found or there are no longer any more places to look (i.e., low > high). Here is the code:
def search(x, nums)
low = 0
high = len(nums) - 1
while low <= high: # There is still a range to search
mid = (low + high) / 2 # position of middle item
item = nums[mid]
if x == item : # Found it! Return the index
13.1. Searching 429
return mid
elif x < item: # x is in lower half of range
high = mid - 1 # move top marker down
else: # x is in upper half
low = mid + 1 # move bottom marker up
return -1 # no range left to search,
# x is not there
This algorithm is quite a bit more sophisticated than the simple linear search.
