MHB Discrete Mathematics Binary Search

[Joystar77]

How many comparisons are performed to find 13 in the following list by using Binary Search?

7, 12, 5, 22, 13, 32

Is it true that there are 10 comparisons performed to find 13 in the following list by using Binary Search? If this isn't right, then can somebody please help explain this to me?

 

[I like Serena]

How many comparisons are performed to find 13 in the following list by using Binary Search?

7, 12, 5, 22, 13, 32

Is it true that there are 10 comparisons performed to find 13 in the following list by using Binary Search? If this isn't right, then can somebody please help explain this to me?

Welcome to MHB, Joystar1977!

You can't really do a binary search on this list.
It needs to be sorted for that.
A linear search would do 5 comparisons, since 13 is the 5th number in the list.
How did you get to 10 comparisons?

 

[Joystar77]

Hello I Like Serena! In response to your questions, I was looking at an example for Binary Search where it says that "binary search relies on a divide and conquer strategy to find a value within an already sorted collection." Maybe I got confused but I thought that since it asked me to do a binary search then I would have to go through each of the numbers twice (7, 12, 5, 22, 13, 32) by pressing start, middle (value), and then the end. I thought that the algorithm was deceptively simple.

 

[I like Serena]

Hello I Like Serena! In response to your questions, I was looking at an example for Binary Search where it says that "binary search relies on a divide and conquer strategy to find a value within an already sorted collection." Maybe I got confused but I thought that since it asked me to do a binary search then I would have to go through each of the numbers twice (7, 12, 5, 22, 13, 32) by pressing start, middle (value), and then the end. I thought that the algorithm was deceptively simple.

As you said: divide and conquer.

If the list were sorted like (5,7,11,12,13,32), binary search might:
- start with entry 11 and see that 13 is to the right,
- then try 13, and with the 2nd comparison, it would be done.

As you can see, if the list is sorted, binary search needs way less comparisons than a linear search.

 

[Joystar77]

Thank you so much for explaining this to me I Like Serena! I really and truly do appreciate it.
Joystar1977