Working of Binary Search

About binary search

It is used to find whether a number is present in a sorted list or not efficiently.

Problem statement

Find whether 4 is present in this arr = [1,3,4,7,8,9] or not.

#include<iostream>
using namespace std;

int main(){
    vector<int> arr = {1,3,4,7,8,9};
    int key = 4;

    int n = arr.size();
    int low=0, mid, high = n-1;
    bool ans = -1;

    while(low<=high){
        mid = (low+high)/2;
        if(arr[mid] > key){ // maybe present in left side
            high = mid-1;  // search left side
        }
        else if(arr[mid] < key){ // maybe present in right side
            low = mid+1;  // search right side
        }
        else{ // found
            ans = mid;
            break;
        }

        if(ans != -1){
            cout<<"Found at : "<<ans<<endl;
        }
        else{
            cout<<"Not Found!"<<endl;
        }
    }
    return 0;
}

Time Complexity: O(LogN)