Binary Search in JAVA

July 28, 2020

Binary Search in JAVA

Binary search is a searching technique that is based upon the Divide-and-Conquer Rule. In this searching technique, a sorted array is divided into two equal halves and then the same technique is applied onto the two halves searching for the element by comparing the high and the low.

Binary-Search-in-JAVA

Working of binary search in JAVA

  1. For Binary Search to be performed on any array, the array must be already sorted in any format, that is, either ascending or descending.
  2. Find the middle index of the array/list.
  3. If the middle element is equal to the search element, Stop Searching.
  4. If the element that is to be searched is less then the middle element then consider the first half as a separate list.
  5. Else-If the element that is to be searched is larger then the middle element then consider the second half as a separate list.
  6. Repeat Step 2-3-4-5 Until desired result is found.

 

JAVA Program for Binary Search
Binary Search in JAVA Programming Language

Algorithm of Binary Search in JAVA

  • while(low<=high)
          mid=(low+high)/2;
  • if(a[mid]<search_element)
          low=mid+1;
  • else if(a[mid]>search_element)
          high=mid-1;
  • If found return index
  • Else return -1

Program of Binary Search in JAVA

import java.util.*;
class Main { 
    int search(int arr[], int x) 
    { 
        int l = 0, r = arr.length - 1; 
        while (l <= r) { 
            int m = l + (r - l) / 2;

            if (arr[m] == x)    //if x is in the middle
                return m; 
            if (arr[m] < x) //if x is greater, search the right half
                l = m + 1; 
            else         //if x is smaller, search the left half 
                r = m - 1; 
        } 
        return -1; //not found
    } 
    public static void main(String args[]) 
    { 
        Main s=new Main(); 
        Scanner sc= new Scanner(System.in);
        System.out.println("Enter the element to be searched ");
        int num=sc.nextInt();
        int arr[]={3,5,6,7,10,14,15,75,88,96,99}; 
        int result = s.search(arr, num); 
        if (result == -1) 
            System.out.println("No match found in the Array"); 
        else
            System.out.println("Match found at index " + result); 
    } 
} 

Enter the element to be searched
96
Match found at index 9

Time Complexity
For Binary Search

Best

O(1)

Average

O(log n)

Worst

O(log n)

Space Complexity

O(1)