Answered: Why is binary search algorithm better…

7th Edition

ISBN:9780133594140

Author:James Kurose, Keith Ross

Publisher:James Kurose, Keith Ross

Chapter1: Computer Networks And The Internet

Section: Chapter Questions

Problem R1RQ: What is the difference between a host and an end system? List several different types of end...

Related questions

Question

Why is binary search algorithm better than sequential search?

Expert Solution

Step 1

Sequential search algorithm involves visiting each and every element of the list of elements and see if the matching element is found in the list. This implies that every element is a candidate element. It can in the worst case take n searches if there are n elements in the list.
For example, in the list below if search is made for 1 and if the search is started from the left end then it will take 9 search steps to find the match. If the search is made from the right then it is a lucky scenario and it just takes one step.
But again if we decide to search for element 10 and we decided to search from right then it will again take 9 steps. These are extreme cases but the point is that the worst case scenario if n searches for n elements.

Step 2

For binary search to work the elements should be ordered (sorted) in ascending or descending order. Once we have the list or collection which has been sorted, the binary search algorithm is applied.
The algorithm approaches the problem by dividing the search space into two portions at each stage and does further search in only one of the halves. As a result the total elements to be searched is aproximately halved in each stage.
So if there are 100 elements, then in the first stage only one half is considered for the next stage, in the next stage 25 elements, around 12 elements in the third and so on. The algorithm hence takes approximately (log n) steps if there are n elements.
How this halving approach works is explained in the next step.