2.3 - Searching Algorithms

For a binary search to work, the following is true ...

• Items must be in order

• Items are not stored in any useful order

• Items do not need to be stored in any useful order

For a hash table search to work, the following is true ...

• Items must be in order

• Items are not stored in any useful order

• Items do not need to be stored in any useful order

For a linear search to work, the following is true ...

• Items must be in order

• Items are not stored in any useful order

• Items do not need to be stored in any useful order

Where does a binary search start?

• The middle item

• A hashing function on the key

• The first item

Where does a hash table search start?

• The middle item

• A hashing function on the key

• The first item

Where does a linear search start?

• The middle item

• A hashing function on the key

• The first item

Binary search ...

• Delivers the location of the item to be found unless there is a collision or does not exist

• Halves the set items to search after each comparison until there are no more to check

• Searches each item in the sequence until the item is found or there are no more items to check

Hash table search ...

• Delivers the location of the item to be found unless there is a collision or does not exist

• Halves the set items to search after each comparison until there are no more to check

• Searches each item in the sequence until the item is found or there are no more items to check

Linear search ...

• Delivers the location of the item to be found unless there is a collision or does not exist

• Halves the set items to search after each comparison until there are no more to check

• Searches each item in the sequence until the item is found or there are no more items to check

In binary search ...

• N comparisons are needed

• Usually 1 comparison is needed