Binary Search of an sorted array using C Program Code & Algorithm

Definition:

Binary Search is used for searching in a sorted array in C programming. This search method tests the middle element of the array, if it is too big then repeats the process in the left half of the array and in right half if it is small. In this way, the amount of space that needs to be searched is halved every time, so the time is 0(log n).

Algorithm:

This represents the binary search method to find a required item in a list sorted in increasing order.

INPUT: Sorted LIST of size N, Target Value T

OUTPUT: Position of T in the LIST = I

Let’s Begin:

Step 1: MAX = N

MIN = 1

FOUND = false

Step 2: WHILE (FOUND is false) and (MAX >= MIN)

MID = (MAX + MIN)DIV 2

IF T = LIST [MID]

I = MID

FOUND = true

ELSE IF T < LIST [MID]

MAX = MID – 1

ELSE

MIN = MID + 1

END

Code:

/* program to search for an item using binary search */

#include<stdio.h>

#include<stdlib.h>

//function binary_search
int binary_search(int array[], int value, int size)

{

int found = 0;

int high= size, low=0,mid;

mid=(high+low)/2;

printf(“\n Looking for %d…\n…\n”,value);

while((!found)&&(high>=low))

{

printf(“Low %d Mid %d High %d \n”,low,mid,high);

if(value==array[mid])

found=1;

else if(value<array[mid])

high=mid-1;

else

low=mid+1;

mid=(high+low)/2;

}

return((found)?mid:-1);

}
// main function
void main()

{

int array[20],i,n;

clrscr();

for (i=0;i<20;i++)

{

array[i]=i+1;

}

clrscr();

printf(“\n\n\nPreparing an array ->\n\n”);

printf(“\t List of number before searching. . . \n\n”);

for(i=0;i<20;i++)                 {

printf(“%d “,array[i]);

}

printf(“\nEnter the value you want to search”);

scanf(“%d”,&n);

printf(“Result of search %d\n”,binary_search(array,n,20));

getch();

}

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>