Search This Blog

Monday, April 18, 2011

Find the first occurrence of an integer in sorted array

Normal binary search will return the target randomly if multiple targets are in the given array.  Below is the modified version of binary search, and it is faster than normal binary search since it requires only one comparison with each loop:

    /**
     * find the index of first occurrence of target
     * @param input is a sorted array
     * @param target
     * @return the first index of target or -1
     */
    public static int findFirstOccurence(int[] input, int target) {
        int lower = -1;
        int upper = input.length;

        while (lower + 1 != upper) {
            //avoid overflow.  See here
            int  middle = (lower + upper) >>> 1;

            if (input[middle] < target) {
                lower = middle;
            } else {
                upper = middle;
            }
        }

        if (upper < input.length && input[upper] == target) {
            return upper;
        } else {
            return -1;
        }
    }

The run time of above method is still O(logn).

No comments:

Post a Comment