Post
Ask Question

Binary Search in Java

Introduction

 
In this article, we are going to describe the implementation of a Binary Search in the Java language. So first you should understand what a Binary Search is. A Binary Search is applicable only to a sorted array and any data structure.
 

Binary Search algorithm

 
Generally, to find a value in an unsorted array, we should look through elements of an array one by one, until the searched value is found. In the case that a searched value is absent from the array, we go through all the elements. On average, the complexity of such an algorithm is proportional to the length of the array.
 
The situation changes significantly when an array is sorted. If we know it, the random access capability can be utilized very efficiently to find a searched value quickly. The cost of a searching algorithm reduces to the binary logarithm of the array length. For reference, log2(1 000 000) = 20. It means, that in the worst case, the algorithm requires 20 steps to find a value in a sorted array of a million elements or to say, that it doesn't access the entire array.
 
Algorithm
 
The following figure helps for a better understanding of the Binary Search concept:
 
Binary Search in Java 
 
The algorithm is quite simple. It can be done either recursively or iteratively. The algorithm consists of the following steps:
 
Step 1: Get the middle element;
 
Step 2: If the middle element equals the searched value, the algorithm stops; otherwise, two cases are possible:
  1. Case 1: The searched value is less than the middle element. In this case, go to step 1 to search the half preceding the middle element.
  2. Case 2: The searched value is greater than the middle element. In this case, go to step 1 to search the half following the middle element.
Step 3: Now we should define when iterations should stop. The first case is when the searched element is found. The second one is when subarray has no elements. In that case, we can conclude that the searched value is not present in the array.
 
Example
  1. import java.util.*;  
  2. public class MyBinarySearch  
  3. {  
  4.     public static void main(String[] args)  
  5.     {  
  6.         // this is an integer array with size 10  
  7.         int[] a = new int[15];  
  8.         int searchV = 0, index;  
  9.         System.out.println("Enter 15 numbers");  
  10.         //now we put all the value in a previous define array with help of scanner class  
  11.         Scanner input = new Scanner(System.in);  
  12.         for (int i = 0; i < a.length; i++)  
  13.         {  
  14.             a[i] = input.nextInt();  
  15.         }  
  16.         System.out.print("Enter a number to search for: ");  
  17.         // take the user input which he wants to search  
  18.         searchV = input.nextInt();  
  19.         index = binarySearch(a, searchV);  
  20.         if (index != -1)  
  21.         {  
  22.             System.out.println("Found at index: " + index);  
  23.         } else  
  24.         {  
  25.             System.out.println("Not Found");  
  26.         }  
  27.     }  
  28.     // here we define binary search method  
  29.     static int binarySearch(int[] search, int find)  
  30.     {  
  31.         int start, end, midPt;  
  32.         start = 0;  
  33.         end = search.length - 1;  
  34.         while (start <= end)  
  35.         {  
  36.             midPt = (start + end) / 2;  
  37.             if (search[midPt] == find)  
  38.             {  
  39.                 return midPt;  
  40.             } else if (search[midPt] < find)  
  41.             {  
  42.                 start = midPt + 1;  
  43.             } else  
  44.             {  
  45.                 end = midPt - 1;  
  46.             }  
  47.         }  
  48.         return -1;  
  49.     }  
  50. }  
Output
 
Binary Search in Java
 
Resources


Similar Articles