The Algorithm :

If an array is sorted, there is a more efficient algorithmthan the linear search to search for an element in it. It is called Binary search, also known as halfinterval search, logarithmic search or binary chop.

Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.

Binary search can be used to access ordered data quickly when memory space is tight.

Let us take an array {63, 17, 96, 38, 3, 43, 35, 82, 57, 90} as an example to find 35 using linear search.

As shown in the image the middle value is taken in each step and compared with the value to be searched(i.e. 35). It is eventually found at the second index.

The Code :

import java.util.*;
class binarys
{
    public static void main()
    {
        Scanner sc = new Scanner(System.in);
        int num,j,k;
        int pos = 0,found = 0,start = 0,last = 9,middle = 0; 
        int x[] = {3,17,35,38,43,57,63,82,90,96};
        System.out.println("Enter the number to be searched : ");
        num = sc.nextInt();
        while(start <= last)
        {
            middle = (start+last)/2;
            if(num == x[middle])
            {
                found = 1;
                pos = middle;
                break;
            }
            else if(num > x[middle])
                start = middle + 1;
            else if(num < x[middle])
                last = middle - 1;
        }
        System.out.println("The array is : ");
       for(int i = 0; i < 10; i++)
        {
            
              System.out.print(x[i] + " ");
        }
        System.out.println();
        if(found == 1)
            System.out.println(num + " is found at index number " + pos);
        else
            System.out.println(num + " is not found in the array");
            
        }
    }

The Binary Search Algorithm has :

Worst case performance – O(log2n)

Best case performance – O(1)

Average performance – O(log2n)

Worst case space complexity – O(1)

It is important to note that binary search can only be done if the array is sorted whereas linear search can be done on unsorted arrays and sorted arrays.

The github link for the program is:

https://github.com/AdityaSareen06/java/blob/master/binarys.java

The picture has been taken from :

Icons made by Gregor Cresnar from www.flaticon.com

If you want to read about the linear search algorithm :

Visits: 75

One Reply to “Binary Search”

Leave a Reply

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