How to organize data?
- Differentiate when binary search can be used vs. when to use linear search.
Exercise When would you use linear/binary search to implement Roster.find? Does implementation of find affect the implementation of other operations?
Solution
To have different implementations for find, we must organize the data in different ways. For binary search, the students array must be kept sorted as we add or remove students.
Keeping the students array sorted imposes an extra cost: while a naive add would append the students array with a new student, the "diligent" add must add a new student in a slot where students array remains sorted. That means add must make due diligence to find the right spot, shift elements around to make a gap, and only then insert a new student. This process would be, at least, as costly as performing a linear search.
The choice of implementing binary vs. linear search must be made based on the specification of the problem.
For example: If we happen to have a roster where we add and remove more frequently than search, then we must not impose extra work on those operations. It would be advisable to leave the students array unsorted and have find implement the linear search.
Resources
- There is an article on Medium that reviews Linear vs. Binary search.
- Here is another Medium article that may be of interest to some of you who want to go beyond the scope of this course.