Binary search math, log base 2 (n) issues

In summary: The actual number of steps might be 1, or 2, or 3, or 4, or 5, or 6. The point is that 2.807 is an upper bound. Can you give me a set of seven numbers for which the binary search takes only one step?In summary, Binary search requires O(log2(n)) operations in the worst case, where n is the number of elements in the set. This means that the number of operations needed to find an element using binary search will never exceed log base 2 of n. However, in some cases, the actual number of operations needed may be less than this upper bound. The O notation is used to describe the asymptotic
  • #1
ducmod
86
0

Homework Statement


Hello!
Binary search requires O( log2(n) ) operations in the worst case. My math doesn't add up.
I would be grateful for help.

Homework Equations


For example:
Find number 8 in the set 1234578.

The Attempt at a Solution


The set contains n = 7 elements.
1) take the middle number 4; 4 < 8
2) take the middle number in the right half of the set 7; 7 < 8
3) in the next right half we have only 1 element and it's 8. done.

Thus I've made 3 operations to find the element 8. 2 to the power 3 equals 8, but
there are only 7 elements in the set. Hence, O(log2(n) - 1) operations.

I don't see why it is log2(n).
Thank you!
 
Physics news on Phys.org
  • #2
ducmod said:

Homework Statement


Hello!
Binary search requires O( log2(n) ) operations in the worst case. My math doesn't add up.
I would be grateful for help.

Homework Equations


For example:
Find number 8 in the set 1234578.

The Attempt at a Solution


The set contains n = 7 elements.
1) take the middle number 4; 4 < 8
2) take the middle number in the right half of the set 7; 7 < 8
3) in the next right half we have only 1 element and it's 8. done.

Thus I've made 3 operations to find the element 8. 2 to the power 3 equals 8, but
there are only 7 elements in the set. Hence, O(log2(n) - 1) operations.

I don't see why it is log2(n).
Thank you!
See https://en.wikipedia.org/wiki/Binary_search_algorithm#Performance
 
  • #3
ducmod said:

Homework Statement


Hello!
Binary search requires O( log2(n) ) operations in the worst case. My math doesn't add up.
I would be grateful for help.

Homework Equations


For example:
Find number 8 in the set 1234578.

The Attempt at a Solution


The set contains n = 7 elements.
1) take the middle number 4; 4 < 8
2) take the middle number in the right half of the set 7; 7 < 8
3) in the next right half we have only 1 element and it's 8. done.

Thus I've made 3 operations to find the element 8. 2 to the power 3 equals 8, but
there are only 7 elements in the set. Hence, O(log2(n) - 1) operations.

I don't see why it is log2(n).
Thank you!

Why would you say the set {1,2,3,4,5,6,7,8} has seven elements? Count them: there are eight of them!
 
Last edited:
  • #4
Ray Vickson said:
Why would you say the set {1,2,3,4,5,6,7,8} has seven elements? Count them: there are eight of them!
Ray, please, take a look at my example, it has 7 elements :) I don't have 6 in the set :)
 
  • #5
ducmod said:

Homework Statement


Hello!
Binary search requires O( log2(n) ) operations in the worst case. My math doesn't add up.
I would be grateful for help.

Homework Equations


For example:
Find number 8 in the set 1234578.

The Attempt at a Solution


The set contains n = 7 elements.
1) take the middle number 4; 4 < 8
2) take the middle number in the right half of the set 7; 7 < 8
3) in the next right half we have only 1 element and it's 8. done.

Thus I've made 3 operations to find the element 8. 2 to the power 3 equals 8, but
there are only 7 elements in the set. Hence, O(log2(n) - 1) operations.

I don't see why it is log2(n).
Thank you!
You seem not to understand what the O notation means. If x is a variable that can become very large then O(x) is the same as O(x+1) etc.
 
  • #6
ducmod said:

Homework Statement


Hello!
Binary search requires O( log2(n) ) operations in the worst case. My math doesn't add up.
I would be grateful for help.

Homework Equations


For example:
Find number 8 in the set 1234578.

The Attempt at a Solution


The set contains n = 7 elements.
1) take the middle number 4; 4 < 8
2) take the middle number in the right half of the set 7; 7 < 8
3) in the next right half we have only 1 element and it's 8. done.

Thus I've made 3 operations to find the element 8. 2 to the power 3 equals 8, but
there are only 7 elements in the set. Hence, O(log2(n) - 1) operations.

I don't see why it is log2(n).
Thank you!

The ##\log_2(n)## count is an asymptotic, worst-case bound. For ##n = 7## we have ##\log_2(7) \doteq 2.80735##, and no algorithm can take exactly that many steps.
 
  • #7
ducmod said:
Ray, please, take a look at my example, it has 7 elements :) I don't have 6 in the set :)


Right: you got me on that. Good one!
 
  • #8
Ray Vickson said:
The ##\log_2(n)## count is an asymptotic, worst-case bound. For ##n = 7## we have ##\log_2(7) \doteq 2.80735##, and no algorithm can take exactly that many steps.
Does it mean that I have to round numbers like 2.80735, and thus get the answer 3? So, the worst case scenario will require 3 steps when n = 7, correct?
 
  • #9
haruspex said:
You seem not to understand what the O notation means. If x is a variable that can become very large then O(x) is the same as O(x+1) etc.

ducmod said:
Does it mean that I have to round numbers like 2.80735, and thus get the answer 3? So, the worst case scenario will require 3 steps when n = 7, correct?

See https://en.wikipedia.org/wiki/Big_O_notation.
 
  • #10
ducmod said:
Does it mean that I have to round numbers like 2.80735, and thus get the answer 3? So, the worst case scenario will require 3 steps when n = 7, correct?

No: 2.807 is an upper bound on the number of steps, and since the actual number of steps must be an integer, we must have N(steps) ≤ 2.
 

FAQ: Binary search math, log base 2 (n) issues

1. What is binary search?

Binary search is an efficient algorithm used to search for a specific value in a sorted list of elements. It works by repeatedly dividing the list in half and comparing the target value with the middle element. This process continues until the target value is found or the list is exhausted.

2. How does binary search work?

Binary search works by dividing the sorted list in half and comparing the target value with the middle element. If the target value is smaller than the middle element, the search is focused on the first half of the list. If the target value is larger, the search is focused on the second half. This process of dividing and comparing continues until the target value is found or the list is exhausted.

3. 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 complete the search increases logarithmically as the size of the list increases. This makes binary search a very efficient algorithm for searching large sorted lists.

4. What is log base 2?

Log base 2, also known as the binary logarithm, is a mathematical operation that represents the power to which the number 2 must be raised to equal a given number. In the context of binary search, the log base 2 of n represents the number of times the list can be divided in half before it is reduced to a single element.

5. Why is log base 2 used in binary search?

Log base 2 is used in binary search because it represents the number of times the search space can be divided in half. This aligns with the way binary search works, making it a more efficient algorithm compared to other search methods. Additionally, the time complexity of binary search is directly related to the logarithm of the input size, making it a preferred choice for searching large lists of elements.

Similar threads

Why am I encountering the binary system in this problem?
Replies
2
Views
2K
Application of N choose K, unsure of what is happening
Replies
6
Views
1K
Binary search tree, number of nodes formula
Replies
2
Views
2K
Prove that ## \sum_{n\leq x}\frac{\phi(n)}{\sqrt{n}}=Cx^{3/2}+.... ##.
Replies
4
Views
1K
(log√125 + log √27 - √8)/ log 15 - log 2 = 3/2
Replies
16
Views
5K
Is This Proof That 8 Divides n^2 - 1 for Odd n Valid?
Replies
11
Views
4K
Max Comparisons in Binary Search: Understanding Efficiency and Implementation
Replies
2
Views
2K
Probability of getting 5 consecutive heads before 2 consecutive tails
Replies
12
Views
3K
If the log is expressed with base 9 it is equal to:
Replies
5
Views
2K
Number of Paths from O(0,0) to A(7,8) - No (3,4)
Replies
12
Views
2K

Hot Threads

Recent Insights

Back
Top