﻿ Algorithm-binary search

# 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={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;
}
}

}