Binary Search

Searching in an array in O(n) time is good but it can further be optimized O(log n) using a method called Binary search. 

Condition for using Binary Search: Elements of the array must be sorted in either increasing or decreasing order.

For Example, 

int Arr[]={1,2,3,4,5};
int Brr[]={5,3,9,6,7};

In Arr, we can apply Binary search for finding an element as all elements of Arr are sorted in increasing order.

We can not apply Binary Search on Brr as the elements of Brr are random.

Basic Logic

Check the exact middle of the array, 

1. If it is equal to that print it,
2.  if it is less than that of the key element then search on the right of the remaining array, 
3.  if it is greater then search the left side of the remaining array.

Repeat the process until you find the key element you want else return -1.

Detail Process

1. First we initialize 2 variable points at the start and end of the array. And use a while loop with a condition that the start should be always less than the end.

    int s=0; //start
    int e=n; //end
    
    while(s<=e){
    
    }

2. find the middle of the element by doing (s+e)/2. if mid is exactly equal to the key then return it.

    int s=0; //start
    int e=n; //end
    
    while(s<=e){
    
        int mid=(s+e)/2;  //Mid of the array

        if(arr[mid]==key){   //if it is equal then return it
            return mid;
        }
    
    }

3. If the middle is greater than that of the key element that means the key element must be present on the left side of the array. hence we shift the end of the array to mid-1. Now, we only have an array of size n/2, on which we repeat this process

    int s=0; //start
    int e=n; //end
    
    while(s<=e){
    
        int mid=(s+e)/2;  //Mid of the array

        if(arr[mid]==key){
            return mid;
        }
        else if(arr[mid]>key){
            e=mid-1;         //Shif the end to mid-1
        }
    
    }

4. If none of these statements get true then it is clear that the element must be greater than the mid element hence we search in the right part of the array and for that, we shift the start of the array to the position of mid+1.

    int s=0;
    int e=n;
    while(s<=e){
        int mid=(s+e)/2;

        if(arr[mid]==key){
            return mid;
        }
        else if(arr[mid]>key){
            e=mid-1;
        }
        else{
            s=mid+1;   //Relocate start to mid+1
        }
    }

We execute the program till we don't find the element, if the element is not present then return -1.

Time complexity

On each step, the number of elements is getting half. That means the execution time of every step is half that of the previous one. It means the time is being reduced logarithmically. which fetch the time complexity of searching in binary up to O(log n).