Binary Search

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

  1. 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)
  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.
  3. If ITEM< element at the MID index, update END=MID-1 to redefine the end index of the divided list of elements.
  4. If ITEM>element at the MID index, update BEG=MID+1 to redefine the start index of the divided list of elements.
  5. Find new MID= INT(BEG+END)/2
  6. 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

Bin Search Java

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 Python

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

Binary Search C

Be First to Comment

Leave a Reply

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