Binary Search in Java
In this tutorial you will learn about binary search in Java.
Binary search is a searching algorithm that uses divide and conquer technique. The array on which searching is to be done must be sorted in ascending order. The target element is compared with middle element. If it is less than middle element then left half is discarded and if it is greater than middle element then right half is discarded. Now a new middle element is calculated in the remaining half and again comparison is done. This process is repeated until the target element is found.
Worst and average case time complexity: O (log n)
Best case time complexity: O (1)
Also Read: Linear Search in Java
In java we can implement binary search in two ways.
- Using manual way
- Using Arrays.binarySearch() method
Below I have shared example for both the ways.
Binary Search in Java
Manual Way
In this example we will implement the binary search algorithm manually.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
package com; import java.util.Scanner; public class BinarySearchJava { public static void main(String args[]){ Scanner sc = new Scanner(System.in); int a[], i, n, x, first, last, mid; System.out.println("Enter size of array:"); n = sc.nextInt(); a = new int[n]; System.out.println("Enter the array in ascending order:"); for(i=0;i<a.length;++i){ a[i] = sc.nextInt(); } System.out.println("Enter element to search:"); x = sc.nextInt(); first = 0; last = n-1; mid = last/2; while(first<=last){ if(a[mid]==x){ break; } else if(a[mid]>x){ last = mid-1; } else{ first = mid+1; } mid = (first+last)/2; } if(first<=last){ System.out.println("Element found at position "+(mid+1)); } else{ System.out.println("Element not found"); } } } |
Output
Enter size of array:
6
Enter the array in ascending order:
1 3 5 6 7 9
Enter element to search:
6
Element found at position 4
Arrays.binarySearch()
We can directly search for an element in an array by using binarySearch() method of java.util.Arrays class. This method returns the index of element if it is found otherwise returns a negative value.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
package com; import java.util.Arrays; import java.util.Scanner; public class BinarySearchJava { public static void main(String args[]){ Scanner sc = new Scanner(System.in); int a[], i, n, x, pos; System.out.println("Enter size of array:"); n = sc.nextInt(); a = new int[n]; System.out.println("Enter the array in ascending order:"); for(i=0;i<a.length;++i){ a[i] = sc.nextInt(); } System.out.println("Enter element to search:"); x = sc.nextInt(); pos = Arrays.binarySearch(a, x); if(pos>=0){ System.out.println("Element found at position "+(pos+1)); } else{ System.out.println("Element not found"); } } } |
Comment below if you found anything incorrect or have doubts related to above binary search in java programs.
