Paper 2 - Search Algorithms

how do you perform a binary search

1. find the middle item in the ordered list

2. if this is the item you’re looking for then stop the search

3. if not, compare the item you’re looking for to the middle item. 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

4. you will be left with half the size of the original list

5. repeat steps 1-4 on the smaller list and keep going until you find the item you’re looking for

what is a negative about the binary search

the list must be ordered

how do you perform a linear search

1. look at the first item in the unordered list

2. If this item you’re looking for, then stop the search

3. If not, then look at the next item in the list

4. Repeat steps 2-3 until you find the item that you’re looking for or you’ve checked every item

why are linear searches usually used on small lists

they are inefficient

a linear search is much … than a binary search but not as efficient

simpler

what are the benefits of linear search

does not have to be ordered

can be used on any type of list

simpler than a binary search

what is a benefit of binary search

more efficient that a linear search

why are binary searches more suitable for larger lists

takes fewer steps than a linear search