MHB Discrete Mathematics Binary Search

AI Thread Summary
Binary search cannot be applied to an unsorted list, such as 7, 12, 5, 22, 13, 32, because it requires the list to be sorted. In this case, a linear search would be more appropriate, requiring 5 comparisons to find the number 13, as it is the fifth element in the list. The confusion arose from a misunderstanding of the binary search algorithm, which operates on a sorted collection using a divide and conquer strategy. If the list were sorted (e.g., 5, 7, 12, 13, 22, 32), binary search would only need 2 comparisons to find 13. The discussion emphasizes the importance of sorting the list before applying binary search to minimize the number of comparisons needed.
Joystar77
Messages
122
Reaction score
0
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?
 
Technology news on Phys.org
Joystar1977 said:
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?
 
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.
 
Joystar1977 said:
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.
 
Thank you so much for explaining this to me I Like Serena! I really and truly do appreciate it.
Joystar1977
 
Thread 'Is this public key encryption?'

Thread 'Is this public key encryption?'

I've tried to intuit public key encryption but never quite managed. But this seems to wrap it up in a bow. This seems to be a very elegant way of transmitting a message publicly that only the sender and receiver can decipher. Is this how PKE works? No, it cant be. In the above case, the requester knows the target's "secret" key - because they have his ID, and therefore knows his birthdate.
View full post »

Similar threads

MHB How to check if search problem has no solution in depth limit search?
Replies
1
Views
1K
MHB How Can I Easily Tackle Binary and Hexadecimal Problems?
Replies
3
Views
1K
Python Programming Question (Python) - Boolean Binary Search
Replies
8
Views
2K
Python Create a binary search tree in python with the support of variables
Replies
13
Views
4K
MHB When Bubble Sort to sort a list of numbers 7, 12, 5, 22, 13, 32
Replies
6
Views
3K
Python Confused about recursion in python-depth first search-:
Replies
3
Views
1K
Java Java- CompareTo with Binary Search Tree
Replies
3
Views
4K
Python Solving UnboundLocalError for Python Iterative Deepening Depth First Search
Replies
1
Views
1K
Determining Binary Search Running Time & Understanding
Replies
3
Views
1K
What are the pitfalls in implementing binary search?
Replies
2
Views
5K

Hot Threads

Recent Insights

Back
Top