Binary Search Algorithm – GCC Program for UBUNTU

Introduction

Click on the following link to download the PPT of Binary Search Algorithm.

BinarySearchAlgorithm

In computer science, binary search or half-interval search algorithm finds the position of a specified value (the input “key”) within a sorted array. In each step, the algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been found so its index, or position, is returned. Otherwise, if the sought key is less than the middle element’s key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the input key is greater, on the sub-array to the right. If the remaining array to be searched is reduced to zero, then the key cannot be found in the array and a special “Not found” indication is returned.

Implementation

//**********************************************************
// Binary Search Algorithm Implementation
//**********************************************************
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<dos.h>

int sequential(int *a, int n, int x)
{
int i;
for(i=0;i<n;i++)
if((*(a+i)) >= x) return i;
return n;
}

int divnconq(int *a,int n,int x)
{
if (n==0 || x>(*(a+(n-1)))) return n;
else return binrec(&a[0],0,n-1,x);
}

int binrec(int *a,int st, int n,int x)
{
int k;
if(st==n) return st;
k=(st+n)/2;
if(x<=(*(a+k))) return binrec(&a[0],st,k,x);
else return binrec(&a[0],k+1,n,x);
}

void main()
{
int a[100],x,n,i;
struct time t1,t2,t3,t4;
clrscr();

printf(“Enter the total Number of Elements: “);
scanf(“%d”,&n);
printf(“\nEnter %d elements in Ascending Order only: “,n);
for(i=0;i<n;i++)
scanf(“%d”,&a[i]);

printf(“\nNow, Enter the element you want to search: “);
scanf(“%d”,&x);

printf(“\n************** Search Element(SEQUENTIAL) **************”);
printf(“\nPosition (Index) for %d element is %d”,x,sequential(&a[0],n,x));
printf(“\n********************************************************\n”);

printf(“\n************** Binary Search (DIVIDE & CONQUER) **************”);
printf(“\nPosition (Index) for %d element is %d”,x,divnconq(&a[0],n,x));
printf(“\n********************************************************\n\n”);
getch();
}