Binary Search


1. Algorithm:

The binary search algorithm begins by comparing the target value to value of the middle element of the sorted array. If the target value is equal to the middle element's value, the position is returned. If the target value is smaller, the search continues on the lower half of the array, or if the target value is larger, the search continues on the upper half of the array. This process continues until the element is found and its position is returned, or there are no more elements left to search for in the array and a "not found" indicator is returned.

Binary_Search_exam

2. Source code:

#include<stdio.h>
#include<iostream>
using namespace std;
int a[100],n,x;
int Binary_Search(int M[], int N, int X){
int First = 0;
int Last = N - 1;
while (First <= Last){
int Mid = (First + Last)/2;
if (X == M[Mid])
return Mid;
if (X < M[Mid])
Last = Mid - 1;
else
First = Mid + 1;
}
return -1;
}
void Input(){
cout<<"Input number elements of array: "; cin>>n;
for(int i=0;i<n;i++){
cout<<"a["<<i<<"]= "; cin>>a[i];
}
cout<<"Input number which want to search: "; cin>>x;
}
int main(){
Input();
cout<<"Position in Array: "<<Binary_Search(a,n,x);
return 0;
}

3. Result:

Binary_Search_result


Advertisements