Algorithm-binary search


Binary search algorithm


The binary search is used to find an elements in a large and sorted list. In the binary search, the list is divided into two parts-- the first half and the second haft, and the search process starts by comparing the target with the first half or second half of the list. If the target falls in the first half of the list we do not need to search it in the second half of the list.


Example C++code for binary search:



#include <cstdlib>
#include <iostream>
#include <conio.h>


using namespace std;
void insertsort(int dataset[], int n);
int binsearch(int dataset[],int target,int lower, int upper);

int main(){
int arr[5]={23,2,3,34,6};
int pos;

insertsort(arr,5);
pos=binsearch(arr,34,0,4);
if(pos!=-1)
cout<<"The target item was found at location:"<<pos<<".";
else cout<<"The target item was not found in the list."<<endl;

getch();
return 0;

}

int binsearch(int dataset[],int target, int lower,int upper){
while(upper>=lower){

int mid=(lower+upper)/2;

if(target==dataset[mid]) return mid;

else if(target<dataset[mid]) upper=mid-1;

else if(target>dataset[mid]) lower=mid+1;

}

return -1;
}

void insertsort(int dataset[], int n){
int i,j;
for(i=1;i<=n;i++){
int pick_item=dataset[i];
bool inserted=false;
for(j=i-1;j>=0 && inserted!=true;){
if(pick_item<dataset[j])
{
dataset[j+1]=dataset[j];
j--;
dataset[j+1]=pick_item;
}
else inserted=true;
}
}

}



Comments

CAPTCHA image



This website intents to provide free and high quality tutorials, examples, exercises and solutions, questions and answers of programming and scripting languages:
C, C++, C#, Java, VB.NET, Python, VBA,PHP & Mysql, SQL, JSP, ASP.NET,HTML, CSS, JQuery, JavaScript and other applications such as MS Excel, MS Access, and MS Word. However, we don't guarantee all things of the web are accurate. If you find any error, please report it then we will take actions to correct it as soon as possible.