Binary Search in C, C++, Python, Java, Php

---

C Implementation Of Binary Search    , C++ Implementation Of Binary Search    , Python Implementation Of Binary Search    , Java Implementation Of Binary Search    , PHP Implementation Of Binary Search

---

[Sequential search is simple and easy method. It is efficient for small list of elements but highly inefficient for larger lists. In the worst case we have to make “N” comparisons to search the element]

In binary search a particular item/element with a certain key value say “num” is to be searched. Approximately middle entry of the array is located then it is compared with “num”. if value matches then the search becomes successful otherwise  if middle element is greater then “num” it means the element “num” may be present in first half otherwise it may be present in second half.

After  deciding the half, we will repeat the process till either the element is found or the interval becomes empty.

This method is called binary search because at each step we reduce the length of the array to search by half.(2 parts).

 We can imagine the efficiency of the binary search by the fact that in just about 20 steps this method can locate an element in a total of 1 million elements.

Note: Array elements should be sorted (Ascending order)

Algorithm
Binary_search(A,N,NUM)
A :Array containing elements in Ascending order
N :Total elements
NUM: element to search
Step Process
1.   First=0,Last=N-1,Pos=-1
2.   Repeat steps 3 and 4 while (First<=Last and Pos=-1)
3.   Middle=(First+Last)/2
4.   If(A[middle]=num) then
      Pos=middle
      Else
          If(NUM>A[middle]) then
          First=middle+1
          Else
          Last=Middle-1
          [end of if block]
     [end of if block]
5.   If(pos>-1) then
      Pos=pos+1
      Display pos
      Else
      Display “element is not present”
      [end of if block]
6.   Return

Complexity

The complexity is measured by the number of comparisons to locate the element in the array. Each comparison reduces the array size to search by half. Thus the maximum number of key comparisons is approximately 2*log2n as two key comparisons are made each time through the loop.
The running time for the worst case is approximately equal to log2n.
The running time for the average case is approximately equal to the running time for the worst case.

C Binary Search

C Implementation Of Binary Search

/* binary search the numbers should be sorted */
#include<stdio.h>
#include<conio.h>
void main()
{
int a[20],i,n,pos,x;
int first,last,middle;
clrscr();
printf(“enter the size of the array “);
scanf(“%d”,&n);
printf(“enter the elements of the array in sorted order\n”);
for(i=0;i<n;i++)
{
printf(“enter the %d element “,i);
scanf(“%d”,&a[i]);
}
printf(“enter the element to search “);
scanf(“%d”,&x);
/* to search the array */
first=0;
pos=-1;
last=n-1;
while((first<=last) && (pos==-1))
{
middle=(first+last)/2;
if (a[middle]==x)
pos=middle+1;
else
if (x>a[middle])
first=middle+1;
else
last=middle-1;
}
if (pos>-1)
printf(“the element is found at %d position\n”,pos);
else
printf(“the element is not found\n”);
getch();
} 

C++ Binary Search

C++ Implementation of Binary Search

/* binary search */
#include<iostream.h>
#include<conio.h>
int bsearch(int a[],int n,int n1);
void main()
{
int a[20],i,n,item,pos;
clrscr();
cout<<“enter the size of the array “;
cin>>n;
cout<<“enter elements in sorted order”<<endl;
for(i=0;i<n;i++)
{
cout<<“enter the element ” ;
cin>>a[i];
}
cout<<“enter the element to search “;
cin>>item;
pos=bsearch(a,n,item);
if(pos==-1)
cout<<“Element is not present”<<endl;
else
cout<<“Element found at loation “<<pos+1<<endl;
getch();
}
int bsearch(int a[],int n,int item)
{
int first,last,mid,pos;
first=0;
last=n-1;
/* to search the array */
while(first<=last)
{
mid=(first+last)/2;
if (item==a[mid])
return(mid);
else
if (item>a[mid])
first=mid+1;
else
last=mid-1;
}
return(-1);
} 

Python Binary Search

Python Implementation Of Binary Search

def binary_search(n1, num):
    start = 0
    end = len(n1)
    while(start < end):         
        mid = (start + end)//2         
        if(n1[mid] > num):
            end = mid
        elif(n1[mid] < num):
            start = mid + 1
        else:
            return mid
    return -1
n = input('Enter the sorted list of numbers: ')
n1 = n.split()
n1 = [int(x) for x in n1]
num = int(input('The number to search for: '))
index = binary_search(n1, num)
if index < 0:
    print('{} was not found.'.format(num))
else:
    print('{} was found at index {}.'.format(num, index))

Output:

Enter the sorted list of numbers: 2 3 6 9 15 28 98
The number to search for: 15
15 was found at index 4.
>>>

---

C Implementation Of Binary Search    , C++ Implementation Of Binary Search    , Python Implementation Of Binary Search    , Java Implementation Of Binary Search    , PHP Implementation Of Binary Search

---

Tutorials	Technical Questions	Interview Questions
C Programming C++ Programming Class 11 (Python) Class 12 (Python)	C Language C++ Programming Python	C Interview Questions C++ Interview Questions C Programs C++ Programs