Binary Search is a very common search method for datasets that contain large count of elements. It works only if the input data is sorted and you have direct access to the middle element. Binary search is based on the Divide and Conquer Technique of algorithm design.
Algorithm Binary Search
- Initialize the variables BEG, END and MID with first index, last index and index of middle element of the input array. (MID= INT(BEG+END)/2)
- If data at MID index matches that of the ITEM to be search, EXIT after printing the MID as the location of the searched element.
- If ITEM< element at the MID index, update END=MID-1 to redefine the end index of the divided list of elements.
- If ITEM>element at the MID index, update BEG=MID+1 to redefine the start index of the divided list of elements.
- Find new MID= INT(BEG+END)/2
- Repeat steps 2 to 5 while BEG<END
The logic of this search technique is that since the elements are in sorted order so if the middle element does not match the item we are searching for, we can discard one half of the list. If ITEM is less than the middle element, ITEM will be in the first half of list else it will exist in the second half of the list. For this the BEG or END are updated to redefine the list boundaries and reduce the comparisons.
If ITEM is less than the element at MID index, update the END index to discard second half of list. If ITEM is greater than the element at MID index, update the BEG index for discard first half of list.
Binary Search has complexity of O(log n) since the list of elements is halved after each comparison. If the array has N elements than successful search or unsuccessful search will be reported after less than or equal to log(N) comparisons. For example if the list contains 16 elements then you will get the result in maximum 4 comparisons, that whether the element to be searched is in list or not.
Binary Search -Java
import java.io.*;
public class BinSearch
{
//construstor
void BinSearch(int data[], int item)
{
//local variables declaration
int num=0, i=0, beg=0, mid=0, end=0;
//store the count of elements of array in num
num = data.length;
//find mid, comapre item to be searched at middle position of array/subarray and redefine boundaries of array to be searched
beg=0;
end=num-1;
mid=(int)(beg+end)/2;
while((beg<=end)&&(item!=data[mid]))
{
// calculate middle element index
mid=(int)(beg+end)/2;
// Compare middle element with item to be searched
if(item==data[mid])
{
//successful search
System.out.println("Element " + item+ " Found at index "+ mid);
return;
}
// redefine boundaries
else if(item<data[mid])
end=mid-1;
else
beg=mid+1;
}
//unsuccessful search
System.out.println("Element is not in the array!!");
}
public static void main(String args[])
{
//Declare and initialize data array
int data[] = {3,4,5,6,7,8,9};
//create BinSearch object using constructor
BinSearch bs = new BinSearch();
//Call BinSearch method with object name to find index of an element
bs.BinSearch(data,7);
bs.BinSearch(data,3);
bs.BinSearch(data,9);
bs.BinSearch(data,10);
}
}Output
Binary Search -Python
#declare and initialise variable
arr=[]
n=0
i=0
flag=0
#Read the count of elements to be stored in array
n=int(input("Number of elements you want in array--->"))
print("Input ",n, " sorted elements in the array!!")
while i<n:
arr.append(int(input("input value--->")))
i=i+1
#initialise boundaries and calculate index of middle elements from boundary indices
beg=0
end=n-1
mid=int((beg+end)/2)
#read element to be sarched
item=int(input("enter element to search--->"))
while(beg<=end):
if(item==arr[mid]):
#successful search
print("Element ",item," Found at position ",mid+1)
flag=1
break;
#redefine boundaries
elif(item<arr[mid]):
end=mid-1
else:
beg=mid+1
#calculate middle element index
mid=int((beg+end)/2)
#unsuccessful search
if (flag==0):
print("Element is not in the array!!")Output
Binary Search -C
#include<stdio.h>
void main( )
{
// declare variables and data array for storing sorted elements
int data[20], num, item, i, beg, mid, end;
// How many elements will be stored in array
printf("How many elements in array:");
scanf("%d",&num);
printf("Input the elements in sorted order:");
//read the elements
for(i=0;i<num;i++)
scanf("%d",&data[i]);
// ask the user the element to be searched
printf("Which Number to search??");
scanf("%d",&item);
//find mid, comapre item to be searched at middle position of array/subarray and redefine boundaries of array to be searched
beg=0;
end=num-1;
while((beg<=end)&&(item!=data[mid]))
{
// calculate middle element index
mid=(int)(beg+end)/2;
if(item==data[mid])
{
//successful search
printf("Element %d Found at index %d!!\n",item,mid+1);
exit(0);
}
// redefine boundaries
else if(item<data[mid])
end=mid-1;
else
beg=mid+1;
}
//unsuccessful search
printf("Element is not in the array!!");
}Output
Be First to Comment