Binary search if array contains duplicates

Question

Hi,

what is the index of the search key if we search for 24 in the following array using binary search.

array = [10,20,21,24,24,24,24,24,30,40,45]

I have a doubt regarding binary search that how does it works if a array has duplicate values.Can anybody clarify...

Answer 1

The array you proposed has the target value in the middle index, and in the most efficient implementations will return this value before the first level of recursion. This implementation would return '5' (the middle index).

To understand the algorithm, just step through the code in a debugger.

public class BinarySearch {
    public static int binarySearch(int[] array, int value, int left, int right) {
          if (left > right)
                return -1;
          int middle = left + (right-left) / 2;
          if (array[middle] == value)
                return middle;
          else if (array[middle] > value)
                return binarySearch(array, value, left, middle - 1);
          else
                return binarySearch(array, value, middle + 1, right);           
    }

    public static void main(String[] args) {
        int[] data = new int[] {10,20,21,24,24,24,24,24,30,40,45};

        System.out.println(binarySearch(data, 24, 0, data.length - 1));
    }
}