Wednesday, February 6, 2019

Binary Search Program in Java

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 so in the next iteration search is done with in the sub-array start to middle (0 to (n/2-1)) and 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 in Java

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

  1. Interpolation Search Program in Java
  2. Radix Sort Program in Java
  3. Selection Sort Program in Java
  4. Running Dos/Windows Commands From Java Program
  5. Find Maximum And Minimum Numbers in The Given Matrix - Java Program

You may also like-

  1. Reading File in Java Using Scanner
  2. Java Lambda Expression Callable Example
  3. Checking Number Prime or Not Java Program
  4. Spring MVC Exception Handling Example Using @ExceptionHandler And @ControllerAdvice
  5. Encapsulation in Java
  6. Constructor Chaining in Java
  7. Reduction Operations in Java Stream API
  8. Batch Processing in Java JDBC - Insert, Update Queries as a Batch