0
\$\begingroup\$

I am trying to solve this problem:

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

and this is my implementation:

public int searchInsert(int[] numbers, int target) {
    int startIndex = 0;
    int endIndex = numbers.length - 1;
    int midIndex;
    while (startIndex <= endIndex) {
        midIndex = (endIndex - startIndex) / 2 + startIndex;
        if(numbers[midIndex] == target)
            return midIndex;
        else {
            if(numbers[midIndex] > target) {
                if(midIndex <= 0 || numbers[midIndex - 1] < target) {
                    return midIndex;
                }
                endIndex = midIndex - 1;
            }
            else {
                if(midIndex >= numbers.length - 1 || numbers[midIndex + 1] > target) {
                    return midIndex + 1;
                }
                startIndex = midIndex + 1;
            }
        }
    }
    return -1;
}

How can I make it more efficient?

\$\endgroup\$
1
\$\begingroup\$

In Java, the most efficient implementation of this will likely be

public int searchInsert(int[] numbers, int target) {
    int index = Arrays.binarySearch(numbers, target);

    if (index < 0) {
        index = -index - 1;
    }

    return index;
}

With that said, the place where I'd look first are your special cases. Under what circumstances would midIndex be less than 0 or more than numbers.length - 1? Never (if it was, numbers[midIndex] would throw an out of bounds exception). And when will it be equal? When we've found the edge, when endIndex will be less than startIndex.

So simplify

    while (startIndex < endIndex) {
        midIndex = (endIndex - startIndex) / 2 + startIndex;
        if (numbers[midIndex] == target) {
            return midIndex;
        }

        if (numbers[midIndex] < target) {
            startIndex = midIndex + 1;
        }
        else {
            endIndex = midIndex - 1;
        }
    }

    return startIndex;

This will do one extra assignment and outer loop comparison but save two comparisons on every iteration. Since the assignment only involves registers and math, it should be quick (possibly quicker than the comparisons, which have to load the registers from cache if not memory).

Without the extra checks, the code will update either startIndex or endIndex and make the same return. Because startIndex will equal either midIndex or midIndex + 1, the same as was returned in the original code.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.