Binary Search

Algorithm

Summary: In this tutorial, we will learn what is the Binary Search algorithm and how to use the Binary Search algorithm to search an element in an array.

Introduction to Binary Search Algorithm

In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array.

https://en.wikipedia.org/wiki/Binary_search_algorithm

Binary Search is a Divide and Conquer algorithm that is used to search an element in a linear data structure (such as an array, a linked list, etc).

It compares the search element with the middle element of the array.

If they are not equal, the algorithm looks for the search element into either half of the array.

After every unmatched comparison, the algorithm eliminates the half in which the search element cannot lie.

For example, consider the following array:

Binary Search Algorithm

The array is sorted in ascending order and the target element is 9.

Binary search will first compare 9 with the middle element of the array i.e. 3.

Because the middle element is 3 which is less than 9 and the array is in ascending order, the binary search algorithm eliminates the first half of the array knowing 9 cannot lie in the first half.

Binary Search Program

Again the algorithm compares 9 with the middle element of the second half i.e. 7. Results in no match. Knowing 9 is greater than 7, it eliminates the first of the partitioned array.

In the next round, the algorithm compares the target element with the only left element i.e. 9, and the match is found.

Steps for Binary Search in Programming

  1. Initialize the array with values.
  2. Sort the array in ascending order.
  3. Compare the search element with the middle element of the array. If searchElement > array[mid] then step 4, else if searchElement<array[mid] then step 5, else if searchElement==array[mid] then step 6.
  4. Eliminate the first half of the array (i.e. start=mid+1)and repeat step 3 for the second half.
  5. Eliminate the second half (i.e. end=mid-1) and repeat step 3 for the first half.
  6. Output “Found” and End.
  7. If the array index goes out of bounds i.e. start>end then it means the search element is not present in the array. Output “Not Found” and End.

Here is the implementation of the steps in C and Java.

C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
int main()
{
    int array[] = {9, 2 ,6, -5, 3 , 0, 7};
    int start, mid, end, searchElement;
    bool flag = false;
 
    printf("Enter a number to begin search using Binary Search:\n");
    scanf("%d",&searchElement);
 
    //Calculating the size of the array
    int sizeOfArray = sizeof(array)/sizeof(array[0]);
 
    //Sorting the array
    sort(array, sizeOfArray);
 
    start = 0;
    end = sizeOfArray - 1;
 
    while(start<= end){
        mid = (start + end) /2;
        if(array[mid] == searchElement){
            printf("YES %d is present in the array \n",searchElement);
            flag = true;   //Means Found
            break; //Breaking out of loop because no more search operation required
        }
        else if (array[mid] < searchElement){
            start = mid+1;
        }
        else {
            end = mid-1;
        }
    }
 
    if(!flag)  //Means flag == false
        printf("Search Element not Found \n");
 
    return 0;
}
 
void sort(int array[], int sizeOfArray){
 
    int i,j, temp;
 
    //Sorting array using bubble sort
    for(i=0; i< sizeOfArray - 1; i++){
        for(j=0; j<sizeOfArray-i-1; j++){
            if(array[j] > array[j+1]){
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
}

Java

import java.util.Scanner;
 
public class App {
 
    static Scanner in= new Scanner(System.in);
 
    public static void main(String args[]){
 
        int array[] = {9, 2 ,6, -5, 3 , 0, 7};
        int start, mid, end, searchElement;
        boolean flag = false;
 
        System.out.println("Enter a number to begin search using Binary Search:");
        searchElement = in.nextInt();
 
        //Sorting the array
        sort(array, array.length);
 
        start = 0;
        end = array.length - 1;
 
        while(start<= end){
            mid = (start + end) /2;
 
            if(array[mid] == searchElement){
                System.out.println("YES "+ searchElement+" is present in the array ");
                flag = true;   //Means Found
                break; //Breaking out of loop because no more search operation required
            }
            else if (array[mid] < searchElement){
                start = mid+1;
            }
            else {
                end = mid-1;
            }
        }
 
        if(!flag)  //Means flag == false
            System.out.println("Search Element not Found ");
    }
 
    private static void sort(int[] array, int size){
        int i,j, temp;
 
        //Sorting array using bubble sort
        for(i=0; i< size - 1; i++){
            for(j=0; j<size-i-1; j++){
 
                if(array[j] > array[j+1]){
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
    }
}

Output

Binary Search Program with Output
Binary Search Code

In this tutorial, we learned what is Binary Search Algorithm and how to implement binary search algorithm in C and Java.

Leave a Reply

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