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.

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:

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:

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:

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!

Overview

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

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;
}