Binary Search | Data Structures and Algorithms

Binary Search is a searching algorithm for finding an element's position in a sorted array. Binary search looks for a particular item by comparing the middlemost item of the collection. If a match occurs, then the index of the item is returned. If the middle item is greater than the item, then the item is searched in the sub-array to the left of the middle item. Otherwise, the item is searched for in the sub-array to the right of the middle item. This process continues on the sub-array as well until the size of the subarray reduces to zero.

Time complexity: O(logn)

Auxiliary Space: O(1)

Follow the given steps to solve the problem:

• Begin with the mid element of the whole array as a search key.

• If the value of the search key is equal to the item then return an index of the search key.

• Or if the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half.

• Otherwise, narrow it to the upper half.

• Repeatedly check from the second point until the value is found or the interval is empty.

#include <iostream>
using namespace std;

int ascendingOrderBinarySearch(int array[],int target,int start,int end)
{
    while(start <= end)
    {
        int mid = start + (end - start)/ 2;

        if(target > array[mid])
        {
            start = mid + 1;
        }
        else if(target < array[mid])
        {
            end = mid - 1;
        }
        else{
            return mid;
        }
    }

    return -1;   
}

int descendingOrderBinarySearch(int array2[],int target,int start,int end)
{

    while(start <= end)
    {
        int mid = start + (end - start)/ 2;

        if(target > array2[mid])
        {
           end = mid - 1;
        }
        else if(target < array2[mid])
        {
           start = mid + 1;
        }
        else{
            return mid;
        }
    }

    return -1;
}

int main() {
    int array[]={1, 2, 3, 4, 5, 6, 8, 19, 23};
    int array2[]={23, 19, 8, 6, 5, 4, 3, 2, 1};

    int size = sizeof(array)/sizeof(array[0]);

    int target= 3;

    int target2=19;



    int result1= ascendingOrderBinarySearch(array,target,0,size-1);
    int result2= descendingOrderBinarySearch(array2,target2,0,size-1);

    if(result1 == -1)
    {
        cout<< "Not Found"<<endl;
    }
    else{
        cout<<"Found at index: "<<result1<<endl;
    }
    if(result2 == -1)
    {
        cout<<"Not Found"<<endl;
    }
    else{
        cout<<"Found at index: "<<result2<<endl;
    }

    return 0;
}

Found at index: 2
Found at index: 1