Question

Implement a recursive binary search on an array of 8-byte integers in LEGV8

Answer 1

import java.util.Arrays;
import java.util.Scanner;
 

public class RecursiveBinarySearch {
 
    public static void main(String args[]) {
 
        int[] sortedArray = new int[]{21, 41, 31, 12, 623, 543, 731, 1898};
        Arrays.sort(sortedArray);
 
        System.out.printf("Searching %d using binary search algorithm in %s %n",
                           31, Arrays.toString(sortedArray));
        binarySearch(sortedArray, 31);
 
        System.out.printf("Finding %d in %s by using recursive binary search 
                           algorithm  %n",
                           37, Arrays.toString(sortedArray));
        binarySearch(sortedArray, 37);
 
        System.out.printf("looking %d in array %s by binary search using 
                           recursion %n",
                          623, Arrays.toString(sortedArray));
        binarySearch(sortedArray, 623);
 
        System.out.printf("Binary Search %d in sorted array %s %n", 1898, 
                          Arrays.toString(sortedArray));
        binarySearch(sortedArray, 1898);
 
    }
 
    
    public static void binarySearch(int[] input, int number) {
        int index = binarySearch(input, number, 0, input.length - 1);
        if (index != -1) {
            System.out.printf("Number %d found at index %d %n", number, index);
        } else {
            System.out.printf("Sorry, number %d not found in array %n", number,
                        index);
        }
    }
 
    
    private static int binarySearch(int[] array, int search, int low, int high) {
        //base case
        if (low > high) {
            return -1;
        }
 
        int mid = (low + high) / 2;
 
        
        if (array[mid] == search) {
            return mid;
        } else if (array[mid] < search) {
            return binarySearch(array, search, mid + 1, high);
        } else {
            // last possibility: a[mid] > x
            return binarySearch(array, search, low, mid - 1);
        }
    }
}