Why is the complexity of the binary search Log in base 2?

Question

Considering the implementation of the iterative binary search code:

// Java implementation of iterative Binary Search 
class BinarySearch { 
    // Returns index of x if it is present in arr[], 
    // else return -1 
    int binarySearch(int arr[], int x) 
    { 
        int l = 0, r = arr.length - 1; 
        while (l <= r) { 
            int m = l + (r - l) / 2; 
  
            // Check if x is present at mid 
            if (arr[m] == x) 
                return m; 
  
            // If x greater, ignore left half 
            if (arr[m] < x) 
                l = m + 1; 
  
            // If x is smaller, ignore right half 
            else
                r = m - 1; 
        } 
  
        // if we reach here, then element was 
        // not present 
        return -1; 
    } 
  
    // Driver method to test above 
    public static void main(String args[]) 
    { 
        BinarySearch ob = new BinarySearch(); 
        int arr[] = { 2, 3, 4, 10, 40 }; 
        int n = arr.length; 
        int x = 10; 
        int result = ob.binarySearch(arr, x); 
        if (result == -1) 
            System.out.println("Element not present"); 
        else
            System.out.println("Element found at "
                               + "index " + result); 
    } 
}

The GeeksforGeeks website says the following:

"For example Binary Search (iterative implementation) has O(Logn) time complexity."

My question is what does the division by 2 have to do with logarithm in base 2? What is the relationship between each other? I will use the analogy of 1 pizza (array) to facilitate the understanding of my question:

1 pizza - divided into 2 parts = 2 pieces of pizza 
2 pieces of pizza - divide each piece in half = 4 pieces of pizza 
4 pieces of pizza - divide each piece in half = 8 pieces of pizza 
8 pieces of pizza - divide each piece in half = 16 pieces of pizza

Logₐb = x
b = logarithming
a = base
x = logarithm result

aˣ = b

The values of pieces of pizza are 1, 2, 4, 8 and 16 are similar to logarithms, but I still can't understand what the relationship is. What would be the relationship among logarithming (b), base (a) and the result of logarithm (x) with the division by 2 of a array (pizza)? Would x be the final amount of pieces that I can divide my array(pizza)? Or is the x the number of divisions of my array (pizza)?

Consider `log2(16) = i`. 2 to the power what gives 16? 4 thus `i=4` — Tony Tannous, Nov 25 '20 at 22:07
It's good to learn about logarithms, but O(log N) is the same no matter what base you use for the log. — Matt Timmermans, Nov 26 '20 at 02:35

score 3 · Answer 1 · answered Nov 26 '20 at 19:57

3

Contrary to your belief, O(log(n)) is independent of any base.

answered Nov 26 '20 at 19:57

Exactly @Yves Daoust, but my doubt was more in the relationship between the logarithm and the binary search algorithm. – ricardoramos Nov 26 '20 at 19:59
1

@ricardoramos: the logarithm of a number is roughly the number of times you can halve it until you reach 1. – Nov 26 '20 at 20:25

Mo B. · Answer 2 · 2020-11-26T07:53:18.910

2

If you have a pizza consisting of 16 slices of unit size, how often can you halve it (and throw away one of the halves) until you get a single slice of unit size?

Answer: log2(16) = 4 times

If you have an array of length n, how often can you halve it (and throw away one of the halves) until you get an array slice of length 1?

Answer: log2(n)

More generally, how does an n-ary search algorithm relate to logarithms?

Logₐb = x
b = the size of the array to search
a = the number of slices you get after one cut (all but one are thrown away)
x = the number of cuts you need to make until you get a slice of size 1

edited Nov 26 '20 at 07:53

answered Nov 25 '20 at 22:01

Mo B.

5,307
3
25
42

thanks for your help! However, for my pizza to have 16 pieces, 8 cuts would be necessary. In fact, I don't know if I'm making a wrong relationship between the logarithm and the number of cuts and the number of slices of pizza. – ricardoramos Nov 26 '20 at 00:59
1

You keep asking the wrong question. The question is not: how many cuts are necessary to get 16 slices. But rather: how many cuts are necessary to get a slice of size 1? And that's 4. In other words, like in the algorithm, you cut in half and **throw away one of the halves** at each step. How often can you do that with an array of size 16? – Mo B. Nov 26 '20 at 06:03
1

@ricardoramos not how many times you *cut*, the pizza is *already cut* in 16 slices. Take half of them you get 8. Take half of them a second time, you have 4. You take half a third time and have 2. Take half a fourth time and you have a single slice. This mirrors what happens during a binary search - if you have an array of 16 people finding a particular one would take (at most) 4 operations, each of which halves the (previous) search space. – VLAZ Nov 26 '20 at 06:04
@MoB. thank you very much for all your help! Your comment helped me to understand better. In addition, I also used the following answer: https://stackoverflow.com/a/13093274/2918302 and also watched the video https://www.youtube.com/watch?v=P3YID7liBug from 2:30 onwards. – ricardoramos Nov 26 '20 at 18:49

score 1 · Answer 3 · answered Nov 25 '20 at 22:02

Let's use the same pizza analogy you have, and assume we have 1 whole pizza and we want 8 slices. Every time we cut, we divide by 2 as well.

The first cut means we will have 2 slices. The second cut gives us 4 slices. The third cut results in 8 slices. We made 3 cuts to get to 8 slices. Mathematically, it turns out that there is a relationship with the numbers 2, 3, and 8. The log function connects those numbers accordingly. When we are limited to how much we can divide, that is our base (base = 2). We have a quantity which is 8. The number of operations was lg(8) = 3 (using lg as log of base 2).

The same idea applies to binary search. We divide each section of the array we search by 2, the quantity is whatever our size of the array is, and the number of operations we perform is asymptotically lg(n).

"Every time we cut, we divide by 2 as well." After the first two cuts, you have to fold the pizza for that to remain true, making it a poor example :(. With normal pizza cutting, every cut adds 2 slices, rather than multiplying by 2. — Mooing Duck, Nov 25 '20 at 22:07
@gamjaman, thanks for your help, but 3 cuts to get to 6 slices and not 8 slices. — ricardoramos, Nov 26 '20 at 00:50

ricardoramos · Answer 4 · 2020-11-26T20:34:23.603

Considering the answers, comments and the following video:

StackOverflow response 1
StackOverflow response 2
Binary Search Video

@Mo B. comment:

The question is not: how many cuts are necessary to get 16 slices. But rather: how many cuts are necessary to get a slice of size 1? And that's 4. In other words, like in the algorithm, you cut in half and throw away one of the halves at each step. How often can you do that with an array of size 16?

@Yves Daoust comment: The logarithm of a number is roughly the number of times you can halve it until you reach 1.

My conclusions are:

The logarithm of a array of size n is approximately the number of times we can divide it in half (considering the base = 2) until it reaches the smallest unit of size 1.

If (x = Logₐb) then 1*2ˣ = n
So x = # times you can multiply 1 by 2 until you get to n
Reversing Logic: x = # of times you can divide n by 2 until you get to 1

The example in the figure would be Log₂10 = x, where x is a result that is not exact. However, if I had drawn the array with 16 positions, this would imply Log₂16 = 4, the result 4 is the number of levels or divisions.

Why is the complexity of the binary search Log in base 2?

4 Answers4