Welcome to our community

Be a part of something great, join today!

Discrete Mathematics Binary Search

Joystar1977

Active member
Jul 24, 2013
119
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?
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,854
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?
 

Joystar1977

Active member
Jul 24, 2013
119
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.
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,854
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.
 

Joystar1977

Active member
Jul 24, 2013
119
Thank you so much for explaining this to me I Like Serena! I really and truly do appreciate it.

Sincerely,

Joystar1977