Search Algorithms

Search Algorithms

1. Binary search

   • Search lists that are in numerical or alphabetical order
   • Works by repeatedly dividing in half the portion of the list that could contain the required data item
   • 25 26 28 37 39 40 41 43 56 70 74 81
     • Searching for 37
     • 37 is below 40 so discard the numbers above 40
     • 25 26 28 17 39
     • The middle item is 28 so discard all items less than or equal to 28
     • The algorithm repeats to find 37
     • If 37 isn't found then it is not in the list
   • For sorted longer lists, binary searches are better

2. Linear search

   • Each item gets checked one by one
   • Very slow for long lists
     • Only really used for short lists
   • Look at the first item, if it is this item you're looking for, then you're done. If not, look at the next item. Continue until the item is found.
   • Simpler than a binary search but less efficient