Discrete Mathematics Binary Search

Click For Summary
SUMMARY

The discussion centers on the application of Binary Search to find the number 13 in an unsorted list: 7, 12, 5, 22, 13, 32. It is established that Binary Search cannot be applied directly to unsorted data, which requires sorting first. A linear search would perform 5 comparisons to locate 13, while a correctly implemented Binary Search on a sorted list, such as 5, 7, 12, 13, 22, 32, would only require 2 comparisons. The confusion regarding the number of comparisons stems from misunderstanding the prerequisites for Binary Search.

PREREQUISITES
  • Understanding of Binary Search algorithm principles
  • Knowledge of sorting algorithms and their importance
  • Familiarity with linear search techniques
  • Basic understanding of algorithm complexity
NEXT STEPS
  • Study the implementation of Binary Search on sorted arrays
  • Learn about sorting algorithms like Quick Sort and Merge Sort
  • Explore the time complexity differences between linear search and binary search
  • Practice coding both Binary Search and Linear Search in a programming language of choice
USEFUL FOR

Students of computer science, software developers, and anyone interested in algorithm optimization and search techniques will benefit from this discussion.

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
 

Similar threads

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