Discrete Mathematics Binary Search

In summary, binary search relies on a divide and conquer strategy to find a value within an already sorted collection. In the given list of numbers (7, 12, 5, 22, 13, 32), it is not possible to perform a binary search as the list is not sorted. A linear search would require 5 comparisons to find the value 13. However, if the list were sorted, binary search would only require 2 comparisons to find the same value. Therefore, sorting the list beforehand can significantly reduce the number of comparisons needed in binary search.
  • #1
Joystar77
125
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
  • #2
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?
 
  • #3
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.
 
  • #4
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.
 
  • #5
Thank you so much for explaining this to me I Like Serena! I really and truly do appreciate it.
Joystar1977
 

FAQ: Discrete Mathematics Binary Search

1. What is Discrete Mathematics?

Discrete Mathematics is a branch of mathematics that deals with discrete structures and objects, rather than continuous ones. It includes topics such as logic, set theory, combinatorics, and graph theory.

2. What is Binary Search?

Binary Search is a search algorithm used to find a specific target value within a sorted list of elements. It works by repeatedly dividing the search space in half, eliminating the half that does not contain the target value.

3. How does Binary Search work?

To perform a Binary Search, the list of elements must be sorted in ascending or descending order. The algorithm then starts by comparing the target value with the middle element of the list. If the target value is smaller, the search is continued in the lower half of the list. If the target value is larger, the search is continued in the upper half of the list. This process is repeated until the target value is found or the search space is empty.

4. What is the time complexity of Binary Search?

The time complexity of Binary Search is O(log n), where n is the number of elements in the list. This means that the time it takes to perform a Binary Search will increase logarithmically as the size of the list increases. It is a very efficient search algorithm for large lists.

5. What are the advantages of using Binary Search?

Binary Search is a very efficient algorithm for searching through large, sorted lists. It has a time complexity of O(log n) and is much faster than linear search, which has a time complexity of O(n). It is also a simple algorithm to implement and does not require any extra memory space.

Similar threads

MHB How to check if search problem has no solution in depth limit search?
Replies
1
Views
965
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
973
Java Java- CompareTo with Binary Search Tree
Replies
3
Views
3K
Python Solving UnboundLocalError for Python Iterative Deepening Depth First Search
Replies
1
Views
1K
MHB What Are the Results of Using Custom Binary Operators in Mathematical Equations?
Replies
1
Views
745
Determining Binary Search Running Time & Understanding
Replies
3
Views
1K

Hot Threads

Recent Insights

Back
Top