Question

Write a recursive method to implement Binary Search of a sorted integer array. Signature of method could be

public int BinarySearch(int target, int low, int high)

Answer 1

Inorder to perform binary search on a sorted integer array , we need to have an array in the program which needed to be passed to the function. But in the question it is mentioned that the siganture of methos could be :

public int BinarySearch(int target, int low, int high). Since an array also neede to be passed to the method , to perform the operation, my take on this would be that the signature of the function should be like :

public int BinarySearch(int a[] , int target, int low, int high) where "a[]" will be the integer array we'll be using.

Since it is a sorted array, I haven't coded the program asking for user input for elements of the array but the I have declared and initilaised the array inside the program itself as well as the target , which is the element to be searched for. You can always change the code to a user input one , if you wish to do so.

PROGRAM CODE

import java.util.*;
class Main{  
    //recursive method for binary search
    public static int BinarySearch(int a[], int target, int low, int high){  
        //if array is in order then perform binary search on the array
        if (high>=low){  
            //calculate mid
            int mid = low + (high - low)/2;  

            //if target =a[mid] return mid
            if (a[mid] == target){  
            return mid;  
            }  

            //if a[mid] > target then target is in left half of array
            if (a[mid] > target){  
            return BinarySearch(a, target, low, mid-1);//recursively search for target  
            }else       //target is in right half of the array

            {  
            return BinarySearch(a, target, mid+1, high);//recursively search for target 
            }  
        }  
        return -1;  
    }
        public static void main()
        {  
        //define array and key i,e,target
        int a[] = {1,11,21,31,41,51,61,71,81,91}; 
        System.out.println("Input List: " + Arrays.toString(a));
        int target = 10;  
        System.out.println("\nThe key to be searched:" + target);
        int high=a.length-1;
        //call BinarySearch method 
        int c = BinarySearch(a,target,0,high);  
        //print the result
        if (c == -1)  
            System.out.println("\nKey not found in given list!");  
        else 
            System.out.println("\nKey is found at location: "+ c + " in the list");  
    }  
}

OUTPUT

I have checked the output for two cases as shown below :