CODEWITHSUNDEEP
javaarrayssearchbinaryduplicates
user2152012
user2152012

Reputation: 159

How to handle duplicate numbers and two or more digit numbers in an array using binary search?

I have written a binary search algorithm it works fine but it does not work properly when there are duplicates or for number two or more digit numbers in the array it returns value not found in the array. What can I do to fix this, will I need to search the array for any duplicates to handle the duplicates? or can I stop the random number generator from generating duplicates?

Here is the code:

public class BinarySearch {

    static int RandomNum;
    static int NumSize;
    static int[] arr;
    static int rangeOfNum;
    static int LookFor;
    static Random numGen = new Random();
    static Scanner Input = new Scanner(System.in);
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("Enter the size of the data set");
        NumSize = Input.nextInt();
        System.out.println("Enter the range of the random numbers");
        rangeOfNum = Input.nextInt();
        arr = new int[NumSize];
        for (int i = 0; i <= NumSize-1; i++) {
            RandomNum = numGen.nextInt(rangeOfNum);
            arr[i] = RandomNum; 
        }
        Arrays.sort(arr);
        for (int i = 0; i < arr.length; i++)
        System.out.println("Number is: " + arr[i]);
        System.out.println("Enter number you want to search for: ");
        LookFor = Input.nextInt();
        binarySearch(arr[0], arr.length-1, LookFor, arr);
    }
    //Binary Search Algorithm
    public static int binarySearch(int LowIndex, int HighIndex, int Target, int[] array) {  
        if (LowIndex <= HighIndex) {
            int MidIndex = (LowIndex + HighIndex)/2;
            if (array[MidIndex] == Target){
                System.out.println("Found target value at index " + MidIndex);
                return Target;}
                else if (array[MidIndex] > Target)
                    return binarySearch(LowIndex, MidIndex-1, Target, array);
                    else 
                        return binarySearch(MidIndex+1, HighIndex, Target, array);
        }
        System.out.println("target value not found");
        return -1;
    }
}

Thanks for the help.

Upvotes: 2

Views: 206

Answers (1)

AndyG
AndyG

Reputation: 41100

The very first time you call binarySearch you call it as follows:

binarySearch(arr[0], arr.length-1, LookFor, arr);

Change it to

binarySearch(0, arr.length-1, LookFor, arr);

Upvotes: 2

Related Questions