Which type of search (linear, binary, or hash) is the best choice for the follow
ID: 3698433 • Letter: W
Question
Which type of search (linear, binary, or hash) is the best choice for the following scenarios? Explain why you would choose that type of search, ensuring that you illustrate what characteristics in the scenario limit and/or support the type of search you can perform [2 marks each]. Assume that you cannot rearrange any of the data in any way. Submit your answers as a .pdf file.
a. You need to find the phone number for a specific person on your contacts list, which is organized alphabetically by name.
b. You want to the first item on your shopping list (e.g. a pair of shoes), in a department store that is organized by department (e.g. food, housewares, clothes, electronics, etc).
c. You want to find the longest word in the dictionary.
d. You are looking at a departures list in an airport (which is sorted by the destination city), and you want to find your flight to Ottawa in the list.
e. You have a record of visits to your website, organized by visit time. You want to find when a specific person last visited your website, and are given only the person's name.
Explanation / Answer
a.Binary search is preferred here.The given list is a sorted one so binary search takes full advantage of it.Here as it is organized alphabetically by name the search starts from the middle and goes halfway forward or backward.It is quite fast and easy to implement.
b.Hash search is preferred bere because the items on the shopping list can be mapped to each department and searching the item within the department is quite easy.However it requires remapping when a new it is added to the list.
c.Dictionary is a sorted list but we are not looking for any particular word hence even if it is a sorted list we cannot take advantage of it using a binary search.Linear search is simple and more effective here.We can start by finding the length of the first word and whenever a word having higher number of letters is encountered replace it and traversing the entire dictionary.
d.Binary search is preferred because the departure list is sorted according to alphabet and starting from the middle element is the preferred option.
e.Hash search using the visit time and the person name as key value pair.Each timestamp is mapped to the person's name.Hash search is most efficient in such circumstances and is more efficient than most indexing systems.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.