• Compare and contrast linear and binary search
• Explain how a linear search works
• Explain how a binary search works
• Explain what special condition the data must be in for a binary search
• Implement a linear search
• Implement a binary search

• linear search
  • items being searched don't have to be in sorted order
  • sorted order allows for a faster algorithm
  • on average, search time is roughly n/2
• binary search
  • items must be in sorted order
  • algorithm is a little more complex than with linear search
  • on average, search time is roughly log n

See testSearches.py for a demo of the number of loops required.

Below is an example of linear vs. binary search times from a Java program.

First linear search: Hits: 99885 Misses: 100115 Elapsed time: 25922.00ms Second linear search: Hits: 99885 Misses: 100115 Elapsed time: 21437.00ms Binary search: Hits: 99885 Misses: 100115 Elapsed time: 63.00ms

linear search def lsearch(ar, key): for i in range(0, len(ar)): if ar[i] == key: return i return -1 lst = [] import random for i in range(2000): lst.append(random.randint(1, 5000)) for i in range(1, 100): print("%3d: %6d" % (i, lsearch(lst, i))) binary search def bsearch(ar, key): low = 0 high = len(ar) - 1 while low <= high: mid = (high + low) // 2 if ar[mid] > key: high = mid - 1 elif ar[mid] < key: low = mid + 1 else: return mid return -1 sorted_lst = lst[:] sorted_lst.sort() for i in range(1, 100): print("%3d: %6d" % (i, bsearch(lst, i)))