3

I'm new to coding, and I'm currently learning searching/sorting algorithms. At the moment, I am working on binary search and had difficulty understanding the time complexity of O(log2 n) for the worst case. Could someone explain to me clearly how to proceed so that I know the logic? (step by step)

Here is the pseudocode:

binarySearch( list, value, low, high ){ 

  if low <= high { 
     mid = (low + high)/ 2

     if value == list[mid]
         return mid

      else if value < list[mid]
         return binarySearch( list, value, low, mid - 1 )

      else
          return binarySearch( list, value, mid+1, high)
      } 

  else
  return -1 
}
TheMathAI
  • 97
  • 6
  • 2
    You can omit the 2 from "log2 n", logs of any base are equivalent to within a constant scale factor of each other and constants are ignored in big-O notation. – pjs Nov 11 '21 at 16:30

2 Answers2

4

Overview

For a moment, forget about your code and take a look at the algorithm on paper, run it through some examples, take a look at some visualizations until you actually understand it.

Have a look at this illustration which I snacked from Wikipedia:

binary search illustration

The search range effectively halves in each round. So you find the number in latest log_2(n) steps.

Guess a number

You might be familiar with the "guess a number game". The game goes like

Think of a number between 0 and 100 but do not tell me the answer yet.

Now, I will try to guess the number and all you can say is:

  • yes, correct answer
  • no, the number is too high
  • no, the number is too low

The optimal strategy for this game is, surprise surprise, binary search. Lets play this through quickly and you will understand better.

The first guess will be 50, since that is in the middle of the current search range [0, 100]. I might say 50 is too high now. That effectively halves the search range down to [0, 49] and the next guess would be 25.

[0, 100], is it 50?
> too high

[0, 49], is it 25?
> too low

[26, 49], is it 38?
> too high

[26, 37], is it 32?
> too high

[26, 31], is it 28?
> too high

[26, 27], is it 27?
> too high

[26], is it 26?
> correct!

You just have witnessed the worst case, all guesses have been wrong until only 26 was left. We found the solution in 7 steps. log_2(100) = 6.64..., so this sounds about correct.

So why log_2?

By now you should have understood that the search range halves in each step. So why does this lead to log_2 mathematically?

It is actually pretty simple. How often can you divide a number by 2 until it is less equals 1? log_2 times. In other words, when does the search range collapse from n numbers down to just 1 number - in exactly1 log_2(n) steps.

1. Technically you have to round it up since there are no "fractions of steps", so ceil(log_2(n)), not that it matters much though.

Note that, due to how Big-O is defined mathematically, O(log_2(n)) and O(log(n)) denote the same set. So you will often just see O(log(n)) (without the 2) being specified as time complexity for binary search.

Code

Finally, let us take a look at your pseudocode and convince ourselves that it is actually the same strategy we just used for the "guess a number" game.

You have your list and low, high indicate the search range. As first step, you select the value in the middle:

mid = (low + high) / 2

in the previous game this was for example how [0, 100] lead to guessing 50 initially, and so on.

Now, you have the actual guess, the lookup:

if value == list[mid]

depending on if it is higher or lower, you cut the search range in halve by calling the method again with a smaller search range. Namely either with

  • low, mid - 1, if the number was too high,
  • or mid + 1, high, if the number was too low.

In the game this is the step where we either go to [0, 49] or to [51, 100], based on whether 50 was too high or too low.

Zabuzard
  • 25,064
  • 8
  • 58
  • 82
  • Wow, that was such a helpful explanation. But, now, if we compare binary search to mergesort, in mergesort we have two O(log(n)) as we split everything and then merge them back. What I don't understand is how can binary search and when we split every element in mergesort is equal in terms of O (both equal to O(log(n)). In binary search, we only check in half of the elements every time compared to mergesort, we split everything until it is a single element. Not sure if it is clear what I am trying to write. – TheMathAI Nov 11 '21 at 18:49
  • Mergesort is not a search algorithm and binary search is not a sorting algorithm. They are unrelated. That said, there are many algorithms that run in the same complexity class. I am not really sure what confuses you here. – Zabuzard Nov 11 '21 at 18:54
  • I'm comparing binary search and mergesort in terms of time complexity to fully understand how to "calculate" (know) the time complexity of an algorithm. From what you explained me to understand the time complexity of binary search, it is because we divide half of the list by 2 every time. So, 1 = N / 2x --> log(n)=x. But for mergesort, we do not divide half of the list every time by two, but we divide both halves of the list by 2 every. So my question is, why is the time complexity of the part where we split everything in mergesort equal to O(log(n)). I may be wrong to compare both algorithms – TheMathAI Nov 11 '21 at 19:06
  • Time complexity analysis is a highly individual thing and you cant "go by pattern". You have to count the amount of statements that are executed depending on `n`. Mergesort consists of two steps: 1) On the downstream, split arrays in halve until you can trivially sort it (size is 1). 2) On the upstream, merge two already sorted arrays sorted (this can be done in `O(k)` using a zipper algorithm with `k` being the size of the arrays you merge. In total this gives you `O(n * log(n))` statements, which is also the lower bound of comparison-based sorting (there are many algos with that complexity). – Zabuzard Nov 12 '21 at 07:55
  • @TheMathAI All of that said, if you want more details you have to ask another question instead of doing this via the comment section :) – Zabuzard Nov 12 '21 at 07:55
2

Binary search searches a sorted array by repeatedly dividing the search interval in half. It starts with an interval covering the whole array. if the value of the search key is less than the item in the middle of the interval, it narrows the interval to the lower half. Otherwise, it narrows it to the upper half. It repeatedly doing this check until the value is found (and return the index value) or the interval is empty and then returns -1.

Ran Turner
  • 14,906
  • 5
  • 47
  • 53