Binary Search Algorithm

Hello, how are you ? Today I shall discuss about binary search algorithm. First of all we know to need why we will use binary search algorithm ? We can use linear search algorithm for searching element in list, but why we will use this ? Because each time we must  remember the time complexity of this program. The time complexity  of  linear search is O(n) where time complexity of binary search is  O(log(n)). We will see that next.

Note: Binary search works on only sorted array.

We will discuss operation, At first you consider a list or array which has some integers type value and you declare three variables left , right and middle. left variable hold first index of this array which is 0, that means 0 is stored in the left variable. right variable holds the last index of this array, but how can we know the index of last variable? first, you will find the size of this array then to subtract 1 from this size, only then you will get the index of last element. Our main target find the search element, we can follow this below process 

To understand this, I will take the help of the above picture. In this picture, we are seeing that there has eight element(size=7) so first index is 0 and last index is 6 (7-1). First we find the middle index of this array. To finding middle index follow this process => (middle = (left +right) / 2 ).

Now we check the value of middle index . If our searching element is same of this value, then we can print this index and say that item is found, but if middle index's value is not same with our value, then what we will do ? then we need check again that our searching value is greater than nor less than value of middle index ?If searching value is greater than the value of middle index than, we sure that the searching value can't stay left side of middle. So we shall set the value of left index with middle index +1 , like this picture L=0 to L=4 (2nd half -> 1st half). Similarly , if searching value is less than the value of middle index, we sure that the searching value can't stay right side of middle, then we shall set the value of right index  with middle index -1 . This process will continue until left index's value is not less than or equal to right index's value. 

#include<stdio.h>
int main()
{
    int a[]={1,2,3,4,5,65,57,87};
    int item=87;
    int left,right,middle;
    left=0;
    right=7;

    while(left<=right){
        middle=(left+right)/2;
        if(a[middle]==item){
            printf("Item found at index: %d\n",middle);
            return 0;
        }else if(a[middle]<item){
            left=middle+1;
        }else{
            right=middle -1;
        }
    }
     printf("Item is not found \n");
    return 0;
}