Binary search (searched value: 6)

Binary search (half-interval search) is a search technique, which finds a position of an input element within a sorted array. Unlike sequential search, which needs at most operations, binary search operates in asymptotic complexity.

Description

Let's suppose that we have an array sorted in descending order and we want to find index of an element e within this array. Binary search in every step picks the middle element (m) of the array and compares it to e. If these elements are equal, than it returns the index of m. If e is greater than m, than e must be located in the left subarray. On the contrary, if , e must be located in the right subarray. At this moment binary search repeats the step on the respective subrarray.

Because the algoritm splits in every step the array in half (and one half of the array is never processed) the input element must be located (or determined missing) in at most steps.

Code

    /**
     * Binary search
     * @param array array sorted in descending order
     * @param leftIndex first index that can be touched
     * @param rightIndex last index that can be touched
     * @param value value to be found
     * @return index of the value in array, or -1 if the array does not contain the value
     */
    public static int binarySearch(int[]  array, int leftIndex, int rightIndex, int value){
        if(leftIndex == rightIndex && array[leftIndex] != value) return -1;
        
        int middleIndex = (leftIndex + rightIndex) / 2;
        if(array[middleIndex] == value) return middleIndex;
        else if(array[middleIndex] > value) 
            return binarySearch(array, middleIndex + 1, rightIndex, value);
        else return binarySearch(array, leftIndex, middleIndex - 1, value);
    }