- Discuss the differences between linear and binary search
- Discuss the advantages and disadvantages of linear and binary search
- Discuss when each type of search should be used
- 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 Search.java: linear and binary search comparison
- Sample run times from Search.java
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