Algorithm: Binary Search

iterative code:

#include<stdio.h>
int binarysearch(int A[],int n,int x)
{
    int low=0, high=n-1;
    while(low<=high)
    {
        int mid=(low+high)/2;  //eta evabeo hoy low+(high-low)/2
        if(x==A[mid])
        {
            return mid;
        }
        else if(x<A[mid])
        {
           high=mid-1; //condition e thakle egula auto return kore
        }
        else if(x>A[mid])
        {
            low=mid+1; //auto return
        }
    }
    return -1; //ekhane nijer moton value chaile boshano jay
}

int main()
{
    int A[]= {2,4,5,7,13,14,15,23};
    printf("Enter a target number:");
    int x;
    scanf("%d",&x);
    int index=binarysearch(A,8,x);
    if(index!=-1)
        printf("Number %d is at index %d",x,index);
    else
        printf("Number %d not found",x);
    return 0;
}

//mathay rakhte hobe function e loop statement e auto return korey while condition er baire gele return korbe -1.. -1 eta return kortese amader nijeder kollane jate index e ei return value niye kaaj korano jay pore

Worst Case: O(logn)

recursive code:

#include<stdio.h>
int binarysearch(int A[],int low,int high,int x)
{
    if(low>high)
    {
        return -1;
    }
    else
    {
        int mid=low+(high-low)/2;
        if(x==A[mid])
        {
            return mid;
        }
        else if(x<A[mid])
        {
            return binarysearch(A,low,mid-1,x);
        }
        else
        {
            return binarysearch(A,mid+1,high,x);
        }
    }
}
int main()
{
    int A[]= {2,6,13,21,36,47,63,81,97};
    int x=63;
    int index=binarysearch(A,0,8,x);
    if(index != -1)
    {
        printf("%d is in index %d",x,index);
    }
    else
    {
        printf("not found %d ",x);
    }
    return 0;
}

Algo Pseudo Code:

Source: http://www.studytonight.com/data-structures/search-algorithms