How to organize data?
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.