Learning Algorithms - Binary Search

Hi guys, If you are familiar with some data structures, it's now time to learn some algorithms. the very basic but very important topic, binary search.

I can code without knowing algorithms, why would I be bothered to learn them?

Of course, you can build software without using algorithms technically and it is not mandatory (I suppose so). However, when you solved your software problem, have you ever questioned yourself "Can I do better?". This is where algorithms come into play, and ultimately, this thought leads you to become a better programmer.

Let me explain why it is important.

Services like Facebook have more than 2.7 billion users, meaning that Facebook engineers presumably have to handle the data of a huge number of users. There are program A and program B to handle those data. Program A takes 1 second to handle each user's data, and 2 seconds for the counterpart. What would be the speed difference between the two programs? Well, you don't even need to calculate them, B takes twice as long as A.

Algorithms are about how efficiently solve a problem, to do that you need to think like computers.
The most widely used algorithms are in search and sort, today I would talk about searching algorithms.

Linear Search

We can't just jump into Binary Search without knowing Linear Search. You must be familiar with this algorithm, that is a method for finding an element within an array using for loop starting from 0 to end of an array. It takes n times as it will check whether the target is in the index each loop this case, from 0 to 5. The time complexity of Linear Search is O(n)

it is seemingly not bad, but can we do better?
Yes, we can make it better by using binary search.

Binary Search

The way it works similar to Linear Search, but the difference is, it will halve of the array, which reduces areas of searching, meaning saving time to search until it found the target.

Let's see this algorithm in real life.

you have a dictionary to find a word, you are looking for the word "glorious". Firstly, you open the dictionary from the middle, and now you are on the M section. Secondly, because the G section is in the front end of the book, no need to look beyond the M section. Thirdly, so you opened again randomly between the beginning and M section and now you are on F section, meaning you will have to look up between F section and M section until you find the G section. You get the idea.

So basically it narrows down your searching region until you found the target.

Let's dive deeper now. we are going to find number 43 from this array [14, 3, 28, 64, 43, 90]. Hold on, we can't really use binary search because it is not in order, it is impossible to figure out ranges of search! Yes… we can only do a binary search when the array is sorted. Let's get it sorted first.

step 1.

So left = 0 and right = arr.length and mid = (left + right) / 2 in this case.

let's check if our current midpoint is the target. Is 28 == 43 true? No! Okay, what do we do now? Because 28 is smaller than 43, we move left pointer to the right of the midpoint.

step 2.

Since we moved left pointer, mid pointer would be again at the middle of left and right, which is now (3 + 5) / 2 = 4 ((left+right) / 2). Let's check again whether we found 43. Is 64(middle) == 43(target) true? No! Then is 64 greater or smaller than 43? 64 is greater than 43. Then we need to move the right pointer to the left of midpoint.

step 3.

Now, the midpoint is at index [3]. So left + right = 6 so midpoint is 6 / 2 = 3. But what if left + right is an odd number that isn't dividable? For example, if left + right is 7 and divides them by 2 gives us 3.5, which is not an integer number that we can use for index. If you are from python background, you will need to use integer divider like so, left + right // 2, which removes decimal point then returns you 3. Is 43(middle) == 43(target) true? Yes, it is! Let's return the mid pointer 3.

How many steps did you take to find 43?

We took 3 steps, if n is a length of the array, we approximately took n/2 steps, which is much shorter than Linear Search, and this will get smaller relative to the size of N, ultimately we are going to save tremendously if the size of N is huge. So we have done half of n work, which can be expressed as 1/2 * 1/2 * 1/2 * 1/2 * 1/2 = log5(Let's assume log base 2). Therefore, the time complexity is O(log2N)

Implementation

There are two ways of implementation in binary search, iterative and recursive. To keep it simple, I will give an iterative example of implementation. In python-like pseudo-code:

def binary_search(arr, target):
  left = 0
  right = arr.length - 1
  while left <= right:
    mid = (left + right) // 2
    # When found target
    if arr[mid] == target:
      return mid
    # When target is less than midpoint value
    elif target < arr[mid]:
      right = mid - 1  # move right pointer to left of mid
    # When target is greater than midpoint value
    else:
      left = mid + 1  # move left pointer to right of mid
  return -1

I hope you find this useful for your computational thinking, I will talk about more of algorithms later! Thank you for reading!

Comments

[Can]

Nice explained!

[Pedro Dantas]

Nice!

[Usman Yahaya]

Thank you. I will look further to more algorithms and data structures👏

[Fernando B 🚀]

Awesome graphics and nice explanation. May I ask what did you use to make the graphics, don't think my handwriting would be as great as yours but I'd still like to know.