Binary search: the math behind 32 steps

In summary: Therefore, if there are 4 billion entries in a phone book, it will take 32 steps to find a specific entry using the binary search algorithm. If the number of entries is increased to 8 billion, it will take 33 steps. The algorithm works by dividing the dataset in half each time, and the number of steps needed is equal to the base 2 logarithm of the number of entries. In this case, the number of steps is equal to ##\log_2(\text{entries})##. Good resources for learning more about this topic include experimenting with smaller numbers of entries and reading about it in textbooks or online resources. Powers of 2 are particularly powerful in this algorithm, as shown by the example of the Wimbledon
  • #1
ducmod
86
0

Homework Statement



Hello!
I have just heard in one online lecture that if for example there is a phone book with 4 billion entries (or a data set
with 4 billion entries), then to find one entry (for example, Kim Simth) I need maximum 32 steps.
If the amount of entries is increased by half, ie to 8 biliion, then it's ll take 33 steps.

I understand the algorithm of how to do binary search (divide by half, by half, etc). But I have no clue on how to
compute the math behind those 32 steps, and how log(n) works in this case.

Please, help me with your advice on how to learn this, what are good resources on this matter, where to read about
it (not in Wikipedia, sorry).

Thank you very much!
 
Physics news on Phys.org
  • #2
Powers of 2 are very powerful ! Play around with 8, 16 entries to see how itt works. Note that the array has to be sorted in order to do this.

Side exercise: if there are 512 contestants at Wimbledon, how many matches have to be played until Djoko gets the first prize ? And how many rounds does that take ? Same thing !
 
  • #3
BvU said:
Powers of 2 are very powerful ! Play around with 8, 16 entries to see how itt works. Note that the array has to be sorted in order to do this.

Side exercise: if there are 512 contestants at Wimbledon, how many matches have to be played until Djoko gets the first prize ? And how many rounds does that take ? Same thing !
I am not sure I correctly understood the nice Wimbledton side task :) Is it 9 steps in worst case scenario? 512 = 2^9, i.e. log 2( 512) = 9
 
  • #4
Nine rounds is right. How would you calculate the total number of matches that it takes ? (this doesn't help with your original post, but it's a nice thingy to carry with you for later on).

Back to the BS (:smile:): If it takes nine steps for 29 entries, how many steps for 232 ? How much is 232 ? The math is really simple, actually! And the number of steps is the 2 logarithm of the number of entries. Piece of cake!
 
  • #5
BvU said:
And the number of steps is the 2 logarithm of the number of entries.
In other words, the number of steps = ##\log_2(\text{entries})##

Here ##\log_2(4) = 2, \log_2(8) = 3##, and so on.
 

Related to Binary search: the math behind 32 steps

1. What is binary search?

Binary search is a search algorithm commonly used in computer science to find the position of a target value within a sorted array. It works by repeatedly dividing the search interval in half until the target value is found or determined to not be present in the array.

2. How does binary search work?

To perform a binary search, the array must first be sorted in ascending or descending order. The algorithm then compares the target value to the middle element of the array. If the target value is smaller, the search is narrowed to the first half of the array. If the target value is larger, the search is narrowed to the second half of the array. This process is repeated until the target value is found or determined to not be present in the array.

3. Why is binary search more efficient than linear search?

Binary search is more efficient than linear search because it eliminates half of the remaining elements in the array with each comparison, resulting in a time complexity of O(log n) compared to linear search's time complexity of O(n).

4. How many steps are required for binary search to find the target value?

In the worst case scenario, binary search requires a maximum of 32 steps to find the target value in an array of 2 billion elements. This is because 2^32 is approximately equal to 2 billion and each step of binary search eliminates half of the remaining elements in the array.

5. What is the significance of 32 steps in binary search?

The number 32 in binary search represents the maximum number of steps required to find the target value in an array of 2 billion elements. It is a constant factor that remains the same regardless of the size of the array, making binary search a highly efficient algorithm for searching large datasets.

Similar threads

Binary search math, log base 2 (n) issues
    • Precalculus Mathematics Homework Help
Replies
9
Views
2K
Proof by induction (Implication)
    • Engineering and Comp Sci Homework Help
Replies
11
Views
4K
I Some questions about Cosmic Inflation
    • Cosmology
Replies
4
Views
2K
Challenge Math Challenge - December 2021
    • Math Proof Training and Practice
3
Replies
93
Views
10K
Challenge Math Challenge - February 2019
    • Math Proof Training and Practice
3
Replies
86
Views
19K
Challenge Math Challenge - December 2018
    • Math Proof Training and Practice
2
Replies
67
Views
10K
Challenge Math Challenge - April 2019
    • Math Proof Training and Practice
3
Replies
83
Views
17K
Help with Logarithms: Binary Searches & Phone Books
    • Introductory Physics Homework Help
Replies
3
Views
4K
Challenge Ready for a Summer Math Challenge?
    • Math Proof Training and Practice
2
Replies
62
Views
8K
Challenge Math Challenge - October 2018
    • Math Proof Training and Practice
3
Replies
71
Views
9K

Hot Threads

Recent Insights

Back
Top