Very concise and efficient solution in Java


  • 16
    B

    I have several solutions to this problem; this is the most concise and efficient one I have.

    public class Solution {
    public int searchInsert(int[] nums, int target) {
        int low = 0, high = nums.length;
        while(low < high) {
            int mid = low + (high - low) / 2;
            if(nums[mid] < target)
                low = mid + 1;
            else
                high = mid;
        }
        return low;
    }
    

    }


  • 1
    S

    +1 nice solution. i've been trying to do this with recursive binary search, and it's giving me a big headache. iterative for this seems much cleaner.


  • 0
    S

    Bruce: I could be wrong, but I think if nums[mid] == target in the some early iteration, ur solution will be potentially wasting calculation cycles by not treating that as one of the cases, although more concise?


  • 0
    B

    It's very good question. As you said, the algorithm does waste a little time for some cases in which @target is found very early. But to support early RETURN, you have to add a IF branch in WHILE block, which costs more time than the former one for general cases. Besides, concise solutions are often easy to understand and therefore to be optimized.


  • 0
    H

    This could be the most concise solution. And the point is: it also handle duplicate!

    Here is the recursive version:

    public int searchInsert(int[] nums, int target) {
        return firstOccurrenceRecur(nums,target,0,nums.length-1);
    }
    public int firstOccurrenceRecur(int[] nums, int target, int low, int high) {
        if (low > high) { return low; }
        int mid = low + ( (high - low) >> 1 );
        if (nums[mid] < target) {
            return firstOccurrenceRecur(nums,target,mid + 1,high);
        } else {
            return firstOccurrenceRecur(nums,target,low,mid-1);
        }
    }

  • 0
    D
    This post is deleted!

  • 1
    C

    Sorry I am a newbie at algorithms. I cannot understand why you assign nums.length to high instead of nums.length - 1.


  • 0

    @Clint_Zhang I think different people have different implementation for binary search, just remember one of them and stick to it.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.