Reduce Time Complexity with Binary Search Algorithm in DSA

ByMorgan
What is the Time Complexity Binary Search Algorithm?

Do you also wanna optimize your searching speed by using binary search algorithm? If yes! You came to right place. Here, in this article we will be learning what exactly binary search is?, How it works? What’s the time complexity of Binary Search Algorithm? and how it will be leads to an optimized solution? so Let’s begin.,

What is Binary Search Algorithm?

Every individual aiming to go for tech MNCs or simply just learning DSA (Data Structure and Algorithm), binary search is one of the first thing, he or she has to learn. So now let’s talk about it what exactly it is. So, Binary is an search algorithm, just like linear search. we can use it to search an element in an array, vector or string. But what’s the difference, the difference lies in it speed or we can say execution speed. Binary Search Algorithm works with super duper speed.

For Example, you have an array of type int with elements 1, 2, 3, 4 and 5. Now, you have to search 4 in that particular array. So normally brute force approach will be linear search like…,

#include <iostream>
using namespace std;

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 4;
    bool found = false;

    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            cout << "Element " << target << " found at index " << i << endl;
            found = true;
            break;
        }
    }

    if (!found) {
        cout << "Element " << target << " not found in the array." << endl;
    }

    return 0;
}

Here, you can see that you have to traverse over the whole array and that’s takes a huge time if we have an array of larger size. In case, you have n number of elements, then time complexity of Linear Search Algorithm will be O(n). Although , it’s good but not optimized and thus Binary Search Algorithm came forward.

How Binary Search Algorithm Works?

Before going on to how binary search algorithm works, let’s talk about the what are the requirements for binary search algorithm to perform accurately. So, there is only single requirement that the array , vector or string on which we are apply binary search algorithm, must be sorted in non-decreasing order. Well! I mean, in ascending order. Now let’s takes the same example of an array of type int with elements 1, 2, 3, 4 and 5 and we have to find .

Cases in Binary Search Algorithm

Before going forward, let me tell you about 3 conditions to use in Binary Search;

  • If the key is equal to middle element, the search ends with a match.
  • If the key is less than the middle element, you only need to search in first half of array as array is sorted.
  • If the key is greater than the middle element, you only need to search in second half of array as array is sorted.

Rough Implementation of Binary Search Algorithm

Now see, how it works? First let me explain in dry format then we will move forward to code. Okay, so first of all we will take mid of the entire array. Let’s say in our case it’s 3 which is at index 2. Right? So now, we will check is it the required the target. In our case, the target is 4 which is not equal to 3. So we will check is it greater or smaller from the target which in our case mid is smaller.

That’s mean we only have to check the later part of array and not the first part. Now again, if we take mid between index 4 to index 5. so the mid will be 4 as it is of type of int and repeat the same process. So in this way we will get our result in an optimized way.

Step 1

left = 0, right = 4
mid = (0 + 4) / 2 = 2

Array:    [1, 2, 3, 4, 5]
Index:     0   1   2   3   4
                     ↑
                   mid = 2 (arr[mid] = 3)

Compare 3 with target (4):
→ 3 < 4, so move the search window to the right half

Step 2

left = 3, right = 4
mid = (3 + 4) / 2 = 3

Array:    [1, 2, 3, 4, 5]
Index:         (previous range)
                     ↓
Index:         3   4
               ↑
             mid = 3 (arr[mid] = 4)

Compare 4 with target (4):
→ Match found!

Output

Element 4 found at index 3

So, now have a look on what exactly done in both algorithm. In linear Search, we need to have four iterations in order to find 4 while in binary search algorithm, we did only 2 iterations to find 4. Let’s see the code, so we can understand it better…,

#include <iostream>
using namespace std;

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 4;

    int left = 0, right = size - 1;
    bool found = false;

    while (left <= right) {
        int mid = (left + right) / 2;

        if (arr[mid] == target) {
            cout << "Element " << target << " found at index " << mid << endl;
            found = true;
            break;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    if (!found) {
        cout << "Element not found." << endl;
    }

    return 0;
}

Here, you can note that, in smaller size searching linear search could be more efficient in some cases but whenever we are solving a problem , we have to look for the worst case! and there, Binary Search Algorithm got a plus point. Let me give you one example to think how fast Binary Search could be. Assume you have array with elements from 0 to 1024 and you have to find 1023. So in linear search, you have to perform 1023 iterations while in binary search algorithm, you only requires only 10 iterations and that’s totally assumed me and you too.

As you already know that in linear search worst case, you have to requires n steps. So, how many steps are required in worst case with binary search algorithm? So, in the worst case, Binary Search requires..,

log2​(n) + 1

Although, This Binary Search is good enough but we can further optimize few more things in it like instead of writing…,

 int mid = (left + right) / 2;

we can use this…,

int mid = left + (right - left) / 2;

As this will handle edges too like, consider a case where;

int left = 2,000,000,000;
int right = 2,000,000,010;

so in this case, normal mid calculation will fails. So, use this one whenever you are trying make-up with Binary Search Algorithm in any language.

What is the Time Complexity of Binary Search Algorithm?

As, we already go up from top to bottom what exactly binary search is? How it’s works? What are requirements and conditions for binary search. I think, you guys are well enough to do more and calculate it’s time complexity. If You already get it hit the comment below with your age, I also want to know, whose my audience. Now let’s make it super quick as we are making are search range shorter with n/2 times. So the time complexity of Binary Search Algorithm is log2(n).

After reading and practice this article, I am damn sure, you have got how to play with it? Am i Right?

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *