Binary search algorithm illustration（2）
Tags: algorithms, cpp
Published: 2021-02-23 09:36:13

Following [previous post](https://dev.to/jemaloqiu/binary-search-algorithm-illustration-1eaj), I would like to illustrate the solution of the following problem (figure below) using **Binary search algorithm**.
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ttgsxr0iewkbpazpmlf9.PNG)
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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rutkm8mxo13137udql0q.png)
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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/scccki7gej68rjhmh0r9.PNG)

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/tnbjhphhej20bbasgcwv.PNG)

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/asay6bqrh7pgbw869jpf.PNG)


## Overview

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

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/dwvrwrr9cce49i1y0t16.PNG)


## C++ Code

```c++
#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;
}
```