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 'Learning Assembly and computer architecture for x86'

Dear Peeps I have posted a few questions about programing on this sectio of the PF forum. I want to ask you veterans how you folks learn program in assembly and about computer architecture for the x86 family. In addition to finish learning C, I am also reading the book From bits to Gates to C and Beyond. In the book, it uses the mini LC3 assembly language. I also have books on assembly programming and computer architecture. The few famous ones i have are Computer Organization and...
View full post »

Thread 'Microsoft Technical Interview question'

I had a Microsoft Technical interview this past Friday, the question I was asked was this : How do you find the middle value for a dataset that is too big to fit in RAM? I was not able to figure this out during the interview, but I have been look in this all weekend and I read something online that said it can be done at O(N) using something called the counting sort histogram algorithm ( I did not learn that in my advanced data structures and algorithms class). I have watched some youtube...
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