DEV Community

Z. QIU
Z. QIU

Posted on

Binary search algorithm illustration(2)

Following previous post, I would like to illustrate the solution of the following problem (figure below) using Binary search algorithm.
Alt Text
As shown in the figure above, we are given a sorted array v = [2, 2, 2, 3, 3, 4, 5, 6, 6, 7] with repeated numbers, and we want to find the index of the first occurrence of target number 3. It's easy for human to find that the answer should be 3 (we suppose index of the first element is 0). How for computers?

Algorithm illustration

As usual, we define three pointers: l, r and mid. They point respectively to the lower (left) bound index, the upper (right) bound index and the middle index of the searching range. We calculate mid as mid = l + (r-l)/2.

Initially, we search the entire array. So l = 0, r = 9 and mid = 4. Here is the first step:
image
Though mid points already to element whose value is equal to 3, we cannot stop searching since we are not sure if its the first occurrence in the array. So we continue to search by changing r to current value of mid. So we narrow down the searching range to the left half of the array: l = 0, r = 4 and mid is updated to 2:

Alt Text

Now the element pointed by mid is 2 and it is smaller than our target number 3. So we narrow down again the searching range to the right half of current searching range. Now l = 3, r = 4 and mid is updated to 3:

Alt Text

Now the element pointed by mid is 3 and it is equal to the target number 3. We now move r to current mid. So l = r = mid = 3. Solution found!

Alt Text

Overview

I put all the steps of this example in one figure to demonstrate overview of the solution:

Alt Text

C++ Code

#include <vector>
#include <iostream>

using namespace std;



/*
* First occurency search 
*/
int foSearch(vector<int>& array, int target) {

    int l = 0, r = array.size()-1;
    while (l<r)
    {
        int mid = l + (r-l)/2;

        if(array[mid] > target)
        {
            r = mid-1;
        }
        else if(array[mid] == target)
        {
            r = mid;
        }
        else{
            l = mid+1;
        }
    }
    cout << "l=" << l <<  ", r=" << r << endl;
    int res = -1;
    if (array[l] == target)
    {
        res = l;
    }

    return res;  
}


int main()
{   
    vector<int> vec {1, 1, 4, 4,9, 9,12,12, 12,32,43, 43,43, 55, 55, 63, 77, 77, 98, 98, 98, 100};
    int ans = foSearch(vec, 43);
    cout << "ans is : " << ans << endl;
    cout << "value is : " << vec[ans] << endl;  

    return 0;
}
Enter fullscreen mode Exit fullscreen mode

Heroku

Simplify your DevOps and maximize your time.

Since 2007, Heroku has been the go-to platform for developers as it monitors uptime, performance, and infrastructure concerns, allowing you to focus on writing code.

Learn More

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more