Introduction
In a binary search, an ordered list is searched for a key starting with the item at the middle of the list. If the item is not found at the location , a determination is made on which half of the list may contain the key, either the upper or lower half. This method is applied to search the midpoint of the half of the list which may contain the key. This repeats until the key is found, or until the search space is reduced to a single location and the list can no longer be divided into halves. If the key is found, the location of the element is returned, otherwise a dummy value is returned (e.g -1)
Binary Search Algorithm
Given a list of items of a finite size and a Key we traverse the list to find the key and output the location of the key found in the list.
Consider the scenario where we have a list, with unique items (in an array) and we wish to find a key:
Algorithm:
//initialization
//Assume our data is stored in an array named list of size N.
list[0..N-1] = {Assume a sorted list}
first=1
last=N-1
result=-1 //used to store the index of a successful search. If result is -1 , the search has failed
middle = (first-last)/2
while (first<=last)
if list[middle]==key then
result= middle
break
else if key<list[middle] then
last=middle;
else
first=middle;
endif
middle=(first-last)/2 + first
endif
endwhile
return result.
Implementation in C code
/*
Demo: Searching a sorted list using
binary search
*/
#include <stdio.h>
#include <stdlib.h>
int binarySearch(int key, int list[], int listSize);
int main()
{
int list[10];
list[0]=5;
list[1]=10;
list[2]=15;
list[3]=20;
list[4]=25;
list[5]=30;
list[6]=35;
list[7]=40;
list[8]=45;
list[9]=50;
int key;
printf("\nenter a search key\n");
scanf("%d",&key);
while (key!=-1)
{
int result = binarySearch(key,list,10);
printf("\nSearch result %d\n",result);
printf("\nenter a search key\n");
scanf("%d",&key);
}
return 0;
}
int binarySearch(int key, int list[], int listSize)
{
/*we use first and last to represent a
portion of the array. Initially, first and last
points to the start of the array and the end of
the array respectively. Middle indexes the location
to the middle of the array.
*/
int result=-1;//-1 represents a failed search
int first=0;
int last=listSize-1;
int middle = (last-first)/2;
while (first<=last)//while first and last have not crossed...
{
if(key==list[middle])//if the key is found....
{
result=middle;
return result;//return the current index and exit function
}
else//the key was not found
{
if(key<list[middle])//if the key would be found
//from first to middle
last=middle-1;//we now search the lower half
else //key would be found from middle to last
first=middle+1;//we now search the upper half
middle=((last-first)/2)+first;//find the new midpoint.
}
}
return result;
}
Alternate Implementation In C using Recursion
/*
Demo: Searching a sorted list using
binary search implemented using recursion
*/
#include <stdio.h>
#include <stdlib.h>
int binarySearch(int key, int list[], int first, int last);
int main()
{
int list[10];
list[0]=5;
list[1]=10;
list[2]=15;
list[3]=20;
list[4]=25;
list[5]=30;
list[6]=35;
list[7]=40;
list[8]=45;
list[9]=50;
int key;
printf("\nenter a search key\n");
scanf("%d",&key);
while (key!=-1)
{
int result = binarySearch(key,list,0,9);
printf("\nSearch result %d\n",result);
printf("\nenter a search key\n");
scanf("%d",&key);
}
return 0;
}
int binarySearch(int key, int list[], int first, int last)
{
/*we use first and last to represent a
portion of the array. Initially, first and last
points to the start of the array and the end of
the array respectively. Middle indexes the location
to the middle of the array.
*/
int result=-1;//-1 represents a failed search
int middle = (last-first)/2+first;
if (first<=last)//if first and last have not crossed...
{
if(key==list[middle])//if the key is found....
{
result=middle;
return result;//return the current index and exit function
}
else//the key was not found
{
if(key<list[middle])//if the key would be found
{ //from first to middle
//we now search the lower half
result= binarySearch(key,list,first,middle-1);
return result;
}
else //key would be found from middle to last
{
result= binarySearch(key,list,middle+1,last);//we now search the upper half
return result;
}
}
}
return result;
}
Updates
2022/2/3
Added introduction paragraph “In a binary … value is returned (e.g -1)“
Added heading “Binary Search Algorithm”
© 2020 Vedesh Kungebeharry. All rights reserved.
Island Class 