Binary Search - Algorithm and Program in C, C++, Python

In this post, we will see about Binary Search, its basic Algorithm, and implementing Binary Search using various programming languages like C, C++, Java, and Python.

INTRODUCTION

Linear Search is a simple searching method that works well for small or unsorted arrays. However, for a large array, the linear search algorithm is very slow. If Array is sorted, we can use another efficient searching method called Binary Search that will increase the speed of search. 

Binary Search begins with a set of data that is sorted. It starts by locating the middle element of the sorted array and comparing it with the search item. If the middle element is equal to the search item then the item is considered to be found and the location of the array element is returned.

If the search item is less than the middle element of the array then the search element if exists must be present before the middle element and searching should be performed in the first half of the array. Otherwise, the second half of the array is searched. The searching continues by checking the middle element in the remaining half of the array. If the search item is not in the middle element in a specified subarray then the search will narrow to half of the remaining part of the array in which elements may appear.

HOW BINARY SEARCH WORKS?

In order to understand binary search, let us considered the sorted array A containing 10 elements. Suppose we want to find the location of an element with a value of 5. 

BINARY SEARCH ALGORITHM

BSEARCH(A, N, ITEM)

Given One dimensional Array, 'A' with 'N' elements whose index ranges from 1 to N and ITEM represents to be searched. This algorithm finds and returns the locations LOC of ITEM in an array or set LOC = -1 if the search is unsuccessful. Here LOC, BEG, MID, END are the local variables. The BEG, MID, and END variables represent the index of the first, middle, and the last element of the array under consideration respectively.

  1. LOC = -1 [ Intialize Location Counter ]

  2. BEG = 1, END = N [ Initialize ]

  3. [ Search for ITEM ]

      Repeat steps 4 and 5 while BEG <= END [ Traverse ]

  4. MID = [ ( BEG + END ) / 2 ]

  5. If ITEM = A[ MID ] then [ Item Found ]

                LOC = MID 

                Exist Loop 

     Else If ITEM > A[ MID ] then [ Look in second half ]

                BEG = MID +1

     Else [ or Look in first half ] 

                END = MID - 1

     [ End of If Structure ]

     [ End of Step 3 Loop ]

6.  Return LOC

1. LOC = -1 [ Intialize Location Counter ] 2. BEG = 1, END = N [ Initialize ] 3. [ Search for ITEM ] Repeat steps 4 and 5 while BEG <= END [ Traverse ] 4. MID = [ ( BEG + END ) / 2 ] 5. If ITEM = A[ MID ] then [ Item Found ] LOC = MID Exist Loop Else If ITEM > A[ MID ] then [ Look in second half ] BEG = MID +1 Else [ or Look in first half ] END = MID - 1 [ End of If Structure ] [ End of Step 3 Loop ] 6. Return LOC

PROGRAM :

#----Binary Search----

array=[]

def takeinput(n):

print("\nEnter "+str(n)+" Elements of Array :")

for i in range(n):

data = int(input())

array.append(data)

#----main----

n = int(input("Enter Number of Element : "))

takeinput(n)

item = int(input("\n\nEnter Element to Search : "))

beg = 0

end = n

mid = int((beg+end)/2)

while(beg<=end):

if array[mid]==item :

print("\nElement Found at Position : "+str(mid+1))

break

elif array[mid]>item :

end = mid - 1

else :

beg = mid + 1

mid = int((beg+end)/2) 

if beg>end :

print("\n\tElement Not Found")

#----Binary Search---- array=[] def takeinput(n): print("\nEnter "+str(n)+" Elements of Array :") for i in range(n): data = int(input()) array.append(data) #----main---- n = int(input("Enter Number of Element : ")) takeinput(n) item = int(input("\n\nEnter Element to Search : ")) beg = 0 end = n mid = int((beg+end)/2) while(beg<=end): if array[mid]==item : print("\nElement Found at Position : "+str(mid+1)) break elif array[mid]>item : end = mid - 1 else : beg = mid + 1 mid = int((beg+end)/2) if beg>end : print("\n\tElement Not Found")

#include<iostream>

using namespace std;

int main()

{

int n;

cout<<"Enter Number of Elements : ";

cin>>n;

int arr[n],s,i,first,last,middle;

cout<<"\nEnter "<<n<<" Elements of Array :\n";

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

{

cin>>arr[i];

}

cout<<"\nEnter Element to Search : ";

cin>>s;

first=0;

last=n;

middle=(first+last)/2;

while(first<=last)

{

if(s==arr[middle])

{

cout<<"\nElement Found at Position : "<<middle+1;

break;

}

else if(s>arr[middle])

{

first=middle+1;

}

else

{

last=middle-1;

}

middle=(first+last)/2;

}

if(first>last)

{

cout<<"\n\tElement Not Found";

}

        return 0;

}

#include<iostream>using namespace std; int main() { int n; cout<<"Enter Number of Elements : "; cin>>n; int arr[n],s,i,first,last,middle; cout<<"\nEnter "<<n<<" Elements of Array :\n"; for(i=0;i<n;i++) { cin>>arr[i]; } cout<<"\nEnter Element to Search : "; cin>>s; first=0; last=n; middle=(first+last)/2; while(first<=last) { if(s==arr[middle]) { cout<<"\nElement Found at Position : "<<middle+1; break; } else if(s>arr[middle]) { first=middle+1; } else { last=middle-1; } middle=(first+last)/2; } if(first>last) { cout<<"\n\tElement Not Found"; } }

#include<stdio.h>
int main()
{
int n;
printf("Enter Number of Elements : ");
scanf("%d",&n);
int arr[n],s,i,first,last,middle;
printf("\nEnter %d Elements of Array :\n",n);
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
printf("\nEnter Element to Search : ");
scanf("%d",&s);
first=0;
last=n;
middle=(first+last)/2;
while(first<=last)
{
if(s==arr[middle])
{
printf("\nElement Found at Position : %d",middle+1);
break;
}
else if(s>arr[middle])
{
first=middle+1;
}
else
{
last=middle-1;
}
middle=(first+last)/2;
}
if(first>last)
{
printf("\n\tElement Not Found");
}
}

#include<stdio.h>int main() { int n; printf("Enter Number of Elements : "); scanf("%d",&n); int arr[n],s,i,first,last,middle; printf("\nEnter %d Elements of Array :\n",n); for(i=0;i<n;i++) { scanf("%d",&arr[i]); } printf("\nEnter Element to Search : "); scanf("%d",&s); first=0; last=n; middle=(first+last)/2; while(first<=last) { if(s==arr[middle]) { printf("\nElement Found at Position : %d",middle+1); break; } else if(s>arr[middle]) { first=middle+1; } else { last=middle-1; } middle=(first+last)/2; } if(first>last) { printf("\n\tElement Not Found"); } }

OUTPUT : 

COMPLEXITY :

In order to determine the complexity of the binary search algorithm, we must know the number of comparisons made between ITEM and A[I] which is sorted.  Therefore the Best Case occurs only when the element we are searching for is present at the middle of the array and in this scenario, Big - O will be expressed as O(1). 

The Worst-Case occurs if the item we are looking for is not present in the array. In that case, the number of comparisons made will be the number of times the loop iterates. On each iteration, the size of the array is reduced by half before the size of the array reaches or goes below 1 (i.e only 1 item left to check). So here in this case Big - O is expressed as O(log₂n).