Binary Search Java

Binary search is a search mechanism for key elements from the given List/Array. In Binary search, the search mechanism is followed by dividing the array into parts; hence the search mechanism is faster. Binary search is faster when compared to linear search; Binary search is faster.

For the binary, the elements in the array must be in sorted order. If the array is not in sorted order, you can sort the array using the Arrays. sort() method.

Binary Search Algorithm

The algorithm for binary search will describe the step by the procedure for searching the required key element. In this search, if the key element is found in the list, then it is a successful search, and it displays the index of the search key element as a result. Otherwise, it returns an unsuccessful search indicating that the key element is not found.

In Binary search, the searching mechanism follows the divide and conquer strategy in which the given array is divided into two parts, the left half and right half. The key element is then compared with the middle value of the list.

Algorithm

Binary_Search(a, lower_value, upper_value, key) // a is the array, a lower value is the first value, an upper value is a final value, and the key is the search element
Step 1: set beginning= lower_value, last = upper_value, position = - 1  
Step 2: repeat steps 3 and 4 while beginning <=last  
Step 3: set middle = (beginning + last)/2  
Step 4: if a[middle] = key  
set position = middle
print position  
go to step 6  
else if a[middle] > key 
set last = middle - 1  
else  
set beginning = middle + 1  
[end of if]  
[end of loop]  
Step 5: if position = -1  
print "The element is not in the list."  
[end of if]  
Step 6: exit  

The above algorithm will describe the process of searching.

BinarySearch.java

class BinarySearch{  
 public static void binarySearch(int arr[], int low, int high, int k){  
   int mid = (low + high)/2;  
   while( low <= high){  
      if ( arr[mid] < k){  
        low = mid + 1;     
      }else if ( arr[mid] == k ){  
        System.out.println("The index of the element: " + mid);  
        break;  
      }else{  
         high = mid - 1;  
      }  
      mid = (low+ high)/2;  
   }  
   if ( low > high ){  
      System.out.println("The key element is not founded");  
   }  
 }  
 public static void main(String args[]){  
        int arr[] = {1,2,3,4,5};  
        int k = 3;  
        int high=arr.length-1;  
        binarySearch(arr,0,high,k);     
 }  
} 

Output:

Binary Search Using Recursion

Binary search can also be done using the recursion.

BinarySearchRecursion.java

class BinarySearchRecursion{  
    public static int binarySearch(int arr[], int low, int last, int key){  
        if (last>=low){  
            int mid = low+ (last - low)/2;  
            if (arr[mid] == key){  
            return mid;  
            }  
            if (arr[mid] > key){  
            return binarySearch(arr, low, mid-1, key);// the left sub array is searched
            }else{  
            return binarySearch(arr, mid+1, last, key);//the right sub array is searched
            }  
        }  
        return -1;  
    }  
    public static void main(String args[]){  
        int arr[] = {1,2,3,4,5};  
        int key = 3;  
        int last=arr.length-1;  
        int res = binarySearch(arr,0,last,key);  
        if (res == -1)  
            System.out.println("The element is not present");  
        else  
            System.out.println("The index of the element: "+res);  
    }  
}  

Output:

Binary search using  Arrays.binarySerach() Method

In the binarySearch() method, the code will be simple. Let us understand this with the simple program.

BinarySearchMethod. java

import java.util.Arrays;  
class BinarySearchMethod{  
    public static void main(String args[]){  
        int arr[] = {1,2,3,4,5};  
        int key = 3;  
        int res= Arrays.binarySearch(arr,key);  
        if (res< 0)  
            System.out.println("The Element is not founded!");  
        else  
            System.out.println("The element found at the index: "+res);  
    }  
}  

Output

This way, the binary search can be in the group of elements. The Time complexity for binary search is O(log N) for the Average case and O(1) in the case of the best case Time Complexity.