Binary Search : Binary search program in C.

RihanCsRihanCs May 12, 2021
binary search program in c

What is Binary Search?

Binary search is an algorithm which uses for searching an element on a sorted array. If array is unsort then array needs to be sort first, before using the binary search algorithm on array. You can make it use of some sorting algorithms, such as the selection sort or the quick sort.

What are the cases in Binary Search? 

The search starts with comparing the given element with middle element of the array.

#Case 1: In this case if the given element is equal to middle element of array. Then middle position (index) will return.
if(arr[mid] == element)

#Case 2: In this case the given element is less than the middle element of the array. Consider the array is sort in an ascending order. Then the second half of the array will be ignore. And the search for the next middle element continues on the first half.
if(arr[mid] > element)

#Case 3: In this case the process is same as Case 2. But when the given element is greater than the middle element of the array. The first half of the array will be ignore. And the search for the next middle element continues on the second half.
if(arr[mid] < element)
The process repeats until the given element is found. If value of the given element is found then the position of the element in array is returned. Binary Search is fast in comparison to linear search.

Example :-

Array : 4  25  13  8  15  20  10  2  7  5
Search element : 5
After sorting - 2  4  5  7  8  10  13  15  20  25

1st iteration - 2  4  5  7  8  10  13  15  20  25
mid[5] = 8 | element < mid

2nd iteration- 2  4  5  7  8  10  13  15  20  25
mid[2] = (4) | element > mid

3rd iteration - 2  4  5  7  8  10  13  15  20  25
mid[3] = (5) | element = mid

Result : Element found at position 3. 

Steps to implement Binary Search. 

  1. Take value of array elements from user.
  2. Take value of ele variable from user to be search in the array.
  3. Sort the array if array is not sort.
  4. Declare three variables (low, mid, high).
  5. Initial value of low, mid and high are 0, array length - 1 and (low+high)/2 respectively.
  6. Use loop and make it's condition low <= high. And code 7,8,9 steps in loop.
  7. First condition element is equal to mid then break the loop.
  8. Second condition element is less than mid then initialize high = mid-1.
  9. Third condition element is greater than mid then initialize low = mid+1.
  10. After loop termination (break) if mid element is equal to element then display array mid position otherwise display that element is not match

Program to implement Binary Search. 

  • Program Implement in C
  • Implement in C++
  • Implement in Java

Recursive program to implement Binary Search. 

  • Program Recursive program implement in C
  • Recursive program implement in C++
  • Recursive program implement in Java

Program Implement in C

#include<stdio.h> // header file for standard input and output
#include<conio.h> // header file for console input and output

// function definition for array sorting
void sort(int *,int);

// main function
int main()
{
    int number[10],ele,posi;
    int min=0,max=9,mid;
    
    // message for user
    printf("\n Enter any 10 number >>| ");
    // take inputs from user
    for(int i=0;i<10;i++)
    {
        scanf("%d",&number[i]);
    }
    
    // use sort function for array sorting 
    sort(number,10);
    // again display the sorted array elements
    printf("\n Here is the sort elements ==> ");
    for(int i=0;i<10;i++)
    {
        printf(" %d,",number[i]);
    }
    
    // ask element from user to search
    printf("\n Which element do you want to search >>| ");
    scanf("%d",&ele);
    // search element
    do{
        // find mid of the range
        mid=(min+max)/2;
        // if element found
        if(number[mid]==ele)
        {
            break;
        }
        else if(number[mid]>ele) // if found element on the mid is greater than searching element
        {
            max=mid-1;
        }
        else if(number[mid]<ele) // if found element on the mid is lesser than searching element
        {
            min=mid+1;
        }
    }
    while(min<=max);

    if(number[mid]==ele) // if element found then display the position of element to the user
    {
        printf(" Element %d found at %d...",ele,mid+1);
    }
    else // if element not found then display the message to the user that element not found
    {
        printf(" Element not found...");
    }
    
    // for holding the screen
    getch();
    return 0;
}

// sorting function definition
void sort(int *arr,int count)
{
    int a;
    // sorting the array elements in assending order
    for(int i=0;i<count-1;i++)
    {
        for(int j=0;j<count-1;j++)
        {
            if(arr[j]>arr[j+1]) // if element is greater than next element then swap elements
            {
                a=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=a;
            }
        }
    }
}

Output :-

 Enter any 10 number >>| 4  25  13  8  15  20  10  2  7  5

 Here is the sort elements ==>  2, 4, 5, 7, 8, 10, 13, 15, 20, 25,
 Which element do you want to search >>| 5
 Element 5 found at 3...


Implement in C++

#include<iostream> // header file for standard input and output
#include<conio.h> // header file for console input and output
using namespace std;

// function definition for array sorting and binary search
void sort(int *,int);

// main function
int main()
{
    int number[10],ele;
    int min=0,max=9,mid;
    
    // message for user
    cout<<"\n Enter any 10 number >>| ";
    // take inputs from user
    for(int i=0;i<10;i++)
    {
        cin>>number[i];
    }
    
    // use sort function for array sorting 
    sort(number,10);
    // again display the sorted array elements
    cout<<"\n Here is the sort elements ==> ";
    for(int i=0;i<10;i++)
    {
        cout<<" "<<number[i]<<",";
    }
    
    // ask element from user to search
    cout<<"\n Which element do you want to search >>| ";
    cin>>ele;
    // search element
    do{
        // find mid of the range
        mid=(min+max)/2;
        // if element found
        if(number[mid]==ele)
        {
            break;
        }
        else if(number[mid]>ele) // if found element on the mid is greater than searching element
        {
            max=mid-1;
        }
        else if(number[mid]<ele) // if found element on the mid is lesser than searching element
        {
            min=mid+1;
        }
    }
    while(min<=max);
    if(number[mid]==ele) // if element found then display the position of element to the user
    {
        cout<<" Element "<<ele<<" found at "<<mid+1<<"...";
    }
    else // if element not found then display the message to the user that element not found
    {
        cout<<" Element not found...";
    }
    
    // for holding the screen
    getch();
    return 0;
}

// sorting function definition
void sort(int *arr,int count)
{
    int a;
    // sorting the array elements in assending order
    for(int i=0;i<count-1;i++)
    {
        for(int j=0;j<count-1;j++)
        {
            if(arr[j]>arr[j+1]) // if element is greater than next element then swap elements
            {
                a=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=a;
            }
        }
    }
}

Output :-

 Enter any 10 number >>| 4  25  13  8  15  20  10  2  7  5

 Here is the sort elements ==>  2, 4, 5, 7, 8, 10, 13, 15, 20, 25,
 Which element do you want to search >>| 5
 Element 5 found at 3...


Implement in Java

import java.util.*;

public class BinarySearch {
    // sorting function definition
    void sort(int arr[], int count) {
        int a;
        // sorting the array elements in assending order
        for (int i = 0; i < count - 1; i++) {
            for (int j = 0; j < count - 1; j++) {
                if (arr[j] > arr[j + 1]) // if element is greater than next element then swap elements
                {
                    a = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = a;
                }
            }
        }
        
        // again display the sorted array elements
        System.out.print("\n Here is the sort elements ==> ");
        for (int i = 0; i < 10; i++) {
            System.out.print(" " + arr[i] + ",");
        }
    }

    public static void main(String[] args) {
        Scanner ss = new Scanner(System.in);
        BinarySearch b = new BinarySearch();
        int number[] = { 5, 45, 1, 21, 5, 44, 75, 65, 14, 35 };
        int ele, min = 0, max = 9, mid;

        // message for user
        System.out.println(" Enter any 10 number >>| 5 45 1 21 5 44 75 65 14 35");
        // use sort function for array sorting
        b.sort(number, 10);

        // ask element from user to search
        System.out.print("\n Which element do you want to search >>| ");
        ele = ss.nextInt();

        // search element
        do {
            // find mid of the range
            mid = (min + max) / 2;
            // if element found
            if (number[mid] == ele) {
                break;
            } else if (number[mid] > ele) // if found element on the mid is greater than searching element
            {
                max = mid - 1;
            } else if (number[mid] < ele) // if found element on the mid is lesser than searching element
            {
                min = mid + 1;
            }
        } while (min <= max);

        if (number[mid] == ele) // if element found then display the position of element to the user
        {
            System.out.print(" Element " + ele + " found at " + (mid + 1) + "...");
        } else // if element not found then display the message to the user that element not
                // found
        {
            System.out.print(" Element not found...");
        }
        ss.close();
    }
}

Output :-

 Enter any 10 number >>| 4  25  13  8  15  20  10  2  7  5

 Here is the sort elements ==>  2, 4, 5, 7, 8, 10, 13, 15, 20, 25,
 Which element do you want to search >>| 5
 Element 5 found at 3...


Recursive program implement in C

#include<stdio.h> // header file for standard input and output
#include<conio.h> // header file for console input and output

// function definition for array sorting
void sort(int *,int);

// main function
int main()
{
    int number[10],ele,posi;
    int min=0,max=9,mid;
    
    // message for user
    printf("\n Enter any 10 number >>| ");
    // take inputs from user
    for(int i=0;i<10;i++)
    {
        scanf("%d",&number[i]);
    }
    
    // use sort function for array sorting 
    sort(number,10);
    // again display the sorted array elements
    printf("\n Here is the sort elements ==> ");
    for(int i=0;i<10;i++)
    {
        printf(" %d,",number[i]);
    }
    
    // ask element from user to search
    printf("\n Which element do you want to search >>| ");
    scanf("%d",&ele);
    // use function to search element
    posi=binary_search(number,ele,0,9);

    if(posi!= -1) // if element found then display the position of element to the user
    {
        printf(" Element %d found at %d...",ele,posi);
    }
    else // if element not found then display the message to the user that element not found
    {
        printf(" Element not found...");
    }
    
    // for holding the screen
    getch();
    return 0;
}

// sorting function definition
void sort(int *arr,int count)
{
    int a;
    // sorting the array elements in assending order
    for(int i=0;i<count-1;i++)
    {
        for(int j=0;j<count-1;j++)
        {
            if(arr[j]>arr[j+1]) // if element is greater than next element then swap elements
            {
                a=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=a;
            }
        }
    }
}

// binary search function definition
int binary_search(int number[],int ele,int min,int max)
{
    if(min>max) // if element not found
    {
        return -1;
    }
    else
    {
        int mid;
        // find mid of the range
        mid=(min+max)/2;
        // if element found
        if(number[mid]==ele)
        {
            return mid+1;
        }
        else if(number[mid]>ele) // if found element on the mid is greater than searching element
        {
            return binary_search(number,ele,min,mid-1);
        }
        else if(number[mid]<ele) // if found element on the mid is lesser than searching element
        {
            return binary_search(number,ele,mid+1,max);
        }
    }
}

Output :-

 Enter any 10 number >>| 4  25  13  8  15  20  10  2  7  5

 Here is the sort elements ==>  2, 4, 5, 7, 8, 10, 13, 15, 20, 25,
 Which element do you want to search >>| 5
 Element 5 found at 3...


Recursive program implement in C++

#include<iostream> // header file for standard input and output
#include<conio.h> // header file for console input and output
using namespace std;

// function definition for array sorting and binary search
void sort(int *,int);
int binary_search(int [],int,int,int);
// main function
int main()
{
    int number[10],ele,posi;
    
    // message for user
    cout<<"\n Enter any 10 number >>| ";
    // take inputs from user
    for(int i=0;i<10;i++)
    {
        cin>>number[i];
    }
    
    // use sort function for array sorting 
    sort(number,10);
    // again display the sorted array elements
    cout<<"\n Here is the sort elements ==> ";
    for(int i=0;i<10;i++)
    {
        cout<<" "<<number[i]<<",";
    }
    
    // ask element from user to search
    cout<<"\n Which element do you want to search >>| ";
    cin>>ele;
    // use function to search element
    posi=binary_search(number,ele,0,9);
    if(posi!= -1) // if element found then display the position of element to the user
    {
        cout<<" Element "<<ele<<" found at "<<posi<<"...";
    }
    else // if element not found then display the message to the user that element not found
    {
        cout<<" Element not found...";
    }
    
    // for holding the screen
    getch();
    return 0;
}

// sorting function definition
void sort(int *arr,int count)
{
    int a;
    // sorting the array elements in assending order
    for(int i=0;i<count-1;i++)
    {
        for(int j=0;j<count-1;j++)
        {
            if(arr[j]>arr[j+1]) // if element is greater than next element then swap elements
            {
                a=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=a;
            }
        }
    }
}

// binary search function definition
int binary_search(int number[],int ele,int min,int max)
{
    if(min>max) // if element not found
    {
        return -1;
    }
    else
    {
        int mid;
        // find mid of the range
        mid=(min+max)/2;
        // if element found
        if(number[mid]==ele)
        {
            return mid+1;
        }
        else if(number[mid]>ele) // if found element on the mid is greater than searching element
        {
            return binary_search(number,ele,min,mid-1);
        }
        else if(number[mid]<ele) // if found element on the mid is lesser than searching element
        {
            return binary_search(number,ele,mid+1,max);
        }
    }
}

Output :-

 Enter any 10 number >>| 4  25  13  8  15  20  10  2  7  5

 Here is the sort elements ==>  2, 4, 5, 7, 8, 10, 13, 15, 20, 25,
 Which element do you want to search >>| 5
 Element 5 found at 3...


Recursive program implement in Java

import java.util.*;

public class BinarySearch {
    // sorting function definition
    void sort(int arr[], int count) {
        int a;
        // sorting the array elements in assending order
        for (int i = 0; i < count - 1; i++) {
            for (int j = 0; j < count - 1; j++) {
                if (arr[j] > arr[j + 1]) // if element is greater than next element then swap elements
                {
                    a = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = a;
                }
            }
        }

        // again display the sorted array elements
        System.out.print("\n Here is the sort elements ==> ");
        for (int i = 0; i < 10; i++) {
            System.out.print(" " + arr[i] + ",");
        }
    }

    // binary search function definition
    int binary_search(int number[], int ele, int min, int max) {
        if (min > max) { // if element not found
            return -1;
        }
        int mid;
        // find mid of the range
        mid = (min + max) / 2;
        // if element found
        if (number[mid] == ele) {
            mid = mid + 1;
        } else if (number[mid] > ele) { // if found element on the mid is greater than searching element
            mid = binary_search(number, ele, min, mid - 1);
        } else if (number[mid] < ele) { // if found element on the mid is lesser than searching element
            mid = binary_search(number, ele, mid + 1, max);
        }
        return mid;
    }

    public static void main(String[] args) {
        Scanner ss = new Scanner(System.in);
        BinarySearch b = new BinarySearch();
        int number[] = { 5, 45, 1, 21, 5, 44, 75, 65, 14, 35 };
        int ele, posi;

        // message for user
        System.out.println(" Enter any 10 number >>| 5 45 1 21 5 44 75 65 14 35");
        // use sort function for array sorting
        b.sort(number, 10);

        // ask element from user to search
        System.out.print("\n Which element do you want to search >>| ");
        ele = ss.nextInt();

        // use function to search element
        posi = b.binary_search(number, ele, 0, 9);

        if (posi != -1) // if element found then display the position of element to the user
        {
            System.out.print(" Element " + ele + " found at " + posi + "...");
        } else // if element not found then display the message to the user that element not
                // found
        {
            System.out.print(" Element not found...");
        }
        ss.close();
    }
}

Output :-

 Enter any 10 number >>| 4  25  13  8  15  20  10  2  7  5

 Here is the sort elements ==>  2, 4, 5, 7, 8, 10, 13, 15, 20, 25,
 Which element do you want to search >>| 5
 Element 5 found at 3...

Attention readers! Don't stop learning now. Check out our articles to gain more knowledge.

Reactions

Post a Comment

0 Comments

If you have any doubt. Let me know.