Binary Search Algorithm!

Binary search is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(log N)¹. 

Here's how it works:

1. Compare x with the middle element.

2. If x matches with the middle element, we return the mid index.

3. Else If x is greater than the mid element, then x can only lie in the right half subarray after the mid element. So we recur for the right half.

4. Else (x is smaller) recur for the left half.

This process continues until the element is found or the subarray is empty.

Look at the array, it is sorted and if we want to find 7 in this array easily by implementing binary search algorithm. We can find it in O(logn) time. While a linear search will take O(n)

time which is very long time. So, if an array is sorted we always use Binary search.

Algorithm:

int main()

{

    optimize();

    int arr[]= {1,4,5,8,10,26};

    int n = sizeof(arr)/sizeof(arr[0]);

    int st=0,en=n-1;

    int target = 8;

    while(st<=en)

    {

        int k = st + (en-st)/2;

        if(arr[k]>target) en = k-1;

        else if(arr[k]<target) st = k+1;

        else{

            cout<<k+1<<endl;

            break;

        }

    }

    return 0;

}

Time complexity: O(n)

STL:

int n = binary_search(sortedarray.begin(), sortedarray.end(), target);

That function will return 1, if target element is present in the array. Otherwise, it will return 0.