Binary Search

Arunima Mandal

Note:

Binary Search is a core algorithm of Computer Science. It can be found everywhere but I am particularly writing it here as I just got to know about new knowledge or change in the logic of the traditional algorithm. The algorithm has been made more appropriate recently with the memory and capacity evolving in recent age. For detail and in-depth knowledge please see this – https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html

So basically in the traditional algorithm while dividing the array or vector space into two halves, the proper logic would be –

mid = first+(last-first)/2;

instead of 

mid = (first+last)/2;

Otherwise, you would get a runtime error in the case that the sum of the first and last is

greater than the maximum positive int value (231 – 1). 

Code:

#include <bits/stdc++.h>

using namespace std;

int a[10000007];
int not_found_pos=-1; //Declaring it global to get the index if the item is not found

bool binarySearch(int item, int n) 
{
    int first=0, last=n-1, mid=0;
    while(first<=last)
    {
        mid=first+(last-first)/2; //for avoiding overflow of summation of first and last
        if(item>a[mid]) first=mid+1;
        else if(item<a[mid]) last=mid-1;
        else return mid; //item=a[mid] //item found
    }
    //Item was not found
    not_found_pos=first; //But if it was found it would be at index 'first'
    return -1; 
}

int main()
{
    int n,item;
    cin>>n;
    for(int i=0; i<n; i++) cin>>a[i]; // Must be sorted.
    cout<<"Enter the item that to be searched"<<endl;
    cin>>item;
    int pos=binarySearch(item,n);
    if(pos==-1)
    {
        cout<<"The item "<<item<<" was not found but if it was found, it would be at index "<< not_found_pos << endl;
    }
    else //Assuming Indexing from "0"
    {
        cout<<"The item "<<item<<" was found at position "<<pos<<endl;
    }
    return 0;
}

Leave a comment