In this post we’ll see how to write Binary search program in Java. Binary search is a divide and conquer algorithm which reduces the range of search by half in each iteration, thus making it more efficient than the Linear search.
How does Binary search work
One of the prerequisite for the Binary search is that the input array should be sorted.
In each iteration searched element is compared with the middle element of the array. If searched element is less than the middle element of the array that means the searched element should be in between the start element to middle element of the array as the array is sorted.
In the next iteration search is done with in the sub-array start to middle (0 to (n/2-1)) or with in the sub-array ((n/2+1) to end) if searched element is greater than the middle element.
This process of division and searching continues unless the element is found or the length of the sub-array becomes 0 which means searched element is not found in the array.
Following image shows the process of division in each iteration
Binary search Java program
Java program for Binary search can be written in both recursive and iterative ways. We’ll see both of these solutions here.
Binary search in Java – Iterative program
public class BinarySearch {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] arr = {12, 23, 10, 34, 55, 4, 68, 3, 73, 99};
Arrays.sort(arr);
System.out.println("sorted array- " + Arrays.toString(arr));
System.out.println("Enter value to search: ");
int searchElement = sc.nextInt();
int index = binarySearch(arr, 0, arr.length-1, searchElement);
if(index != -1){
System.out.println("Searched item " + arr[index] + " found at index "+index);
}else{
System.out.println("Searched item " + searchElement + " not found in the array");
}
}
private static int binarySearch(int[] arr, int start, int end, int searchElement){
while(start <= end){
int middle = (start+end)/2;
System.out.println("start- " + start + " end " + end + " middle- " + middle);
// element found
if(searchElement == arr[middle]){
return middle;
}
// left half
if(searchElement < arr[middle]){
end = middle - 1;
}else{
// right half
start = middle + 1;
}
}
return -1;
}
}
Output
sorted array- [3, 4, 10, 12, 23, 34, 55, 68, 73, 99] Enter value to search: 34 start- 0 end 9 middle- 4 start- 5 end 9 middle- 7 start- 5 end 6 middle- 5 Searched item 34 found at index 5
Binary search in Java – Recursive program
public class BinarySearch {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] arr = {12, 23, 10, 34, 55, 4, 68, 3, 73, 99};
Arrays.sort(arr);
System.out.println("sorted array- " + Arrays.toString(arr));
System.out.println("Enter value to search: ");
int searchElement = sc.nextInt();
int index = binarySearch(arr, 0, arr.length-1, searchElement);
if(index != -1){
System.out.println("Searched item " + arr[index] + " found at index "+index);
}else{
System.out.println("Searched item " + searchElement + " not found in the array");
}
}
private static int binarySearch(int[] arr, int start, int end, int searchElement){
// exit condition
if(start > end){
return -1;
}
int middle = (start+end)/2;
System.out.println("start- " + start + " end " + end + " middle- " + middle);
// element found
if(searchElement == arr[middle]){
return middle;
}
// left half
if(searchElement < arr[middle]){
return binarySearch(arr, start, middle-1, searchElement);
}else{
// right half
return binarySearch(arr, middle+1, end, searchElement);
}
}
}
Output
sorted array- [3, 4, 10, 12, 23, 34, 55, 68, 73, 99] Enter value to search: 55 start- 0 end 9 middle- 4 start- 5 end 9 middle- 7 start- 5 end 6 middle- 5 start- 6 end 6 middle- 6 Searched item 55 found at index 6
Performance of Binary search
Time complexity of Binary search is O(logn).
Space complexity of Binary search is O(1) as no auxiliary space is needed. Though recursive solution will have method stacks for each recursive call making the space complexity as O(logn).
That's all for this topic Binary Search Program in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Programs Page
Related Topics
You may also like-