Search Algorithms

Search Algorithms

1. Binary Search

   • 1. Find the middle item in the ordered list. If it's the item you're looking for, stop the search - oyu've found it
     • 2. If not, compare the item you're looking for to the middle item and get rid of the half of the list it isn't on.
       • If it comes before the middle item, get rid of the second half of the list
       • If it comes after the middle item, get rid of the first half of the list.
       • 3. You'll be left with a list half the size of the original. Repeat steps 1-2 on this new list to make a smaller one. Repeat until you find the item you're looking for.
     • To find the middle item in a list of n items do (n + 1) ÷ 2 and round up if necessary
   • Only works on ordered lists
   • Looks for the middle item and compares it to the searched item

2. Linear Search

   • Works on both ordered and unordered lists
   • Checks each item in a list until it finds the searched item or has checked every item
   • 1. Look at the first item in the list. If this is the item you're looking for then stop the search - you've found it.
     • 2. If this is the item you're looking for then stop the search - you've found it.
       • 3. If not, look at the next item in the list
         • 4. Repeat steps 2-3 until you find the item you're looking for or you've checked every item.

3. Comparisons

   • A linear search is much simpler than a binary search but not as efficient.
     • Linear search can be used on any type of list
       • It is inefficient, so is often only used on small lists
   • Once a list has been ordred, a binary search is more efficient than a linear search
     • Binary searches take fewer steps to find the searched item
       • It is more suitable for large lists of items