My 8 line Java solution


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

  • -44
    J

    Here is my short accept code in C++

    class Solution {
    public:
    int searchInsert(int A[], int n, int target) {
    for ( int i =0; i <= n-1 ; i++){
    if( A[i] == target ){
    return i;
    } else if( A[i] > target ){
    return i;
    }
    }
    return n;
    }
    };


  • 16
    K

    mid = (low + high) / 2 ..if low and high are very big,this line will cause overflow errror...


  • -22
    T
    public class Solution {
    	public int searchInsert(int[] A, int target) {
    		int pos = Arrays.binarySearch(A, target);
    		return (pos < 0)? -pos - 1 : pos;
    	}
    }
    

    Is using Arrays acceptable?


  • 5
    D

    I think we can use: mid = (right - left) / 2 + left; this will prevent overflow.


  • 11
    Q

    could be neater.

    int low = 0, high = A.length;
    while(low<high) {
    	mid=low+(high-low)/2; // low<=mid, mid<high
    	if (nums[mid]>=target) high=mid; // high always decreases (even high-low==1)
    	else low=mid+1; // low always increases
    }
    return low;

  • 0
    S

    qeatzy: I think u r missing something like 'if(nums[mid] == target) return mid;'?


  • 0
    K

    Not exactly, the condition of (nums[mid]==target) and (nums[mid]>=target && nums[mid-1]<target) is same.


  • 2

    Another Java solution:

    public class Solution {
    public int searchInsert(int[] nums, int target) {
      int s = 0, e = nums.length-1;
      while(s < e){
        int m = (s + e)/2;
        if(nums[m] < target) {
          s = m + 1;
        } else if(nums[m] > target) {
          e = m;
        } else return m;
      }
      
      return target > nums[s] ? s + 1: s;
    }
    }

  • 1
    W

    @kaiChristopher yes, so i think low + (high - low) / 2 is better!


  • 0
    G

    @kaiChristopher
    i saw someone use this: mid=left+(right-left)/2 ,you can try this to prevent overflow problem


  • 2
    C

    this my solution:

    public static int searchInsert(int[] nums, int target) {

        if (target<nums[0])
        {
            return 0;
        }
    
        if (target>nums[nums.length-1])
        {
            return nums.length;
        }
    
        for (int i=0;i<nums.length;i++)
        {
            if (nums[i]==target)
            {
                return i;
            }
            if (target>nums[i]&&target<nums[i+1])
            {
                return i+1;
            }
        }
        return 0;
    }

  • 0
    This post is deleted!

  • 0
    L

    public int searchInsert(int[] nums, int target) {
    if(nums.length==0)
    return 0;
    for(int i = 0;i<nums.length;i++){
    if(nums[i]==target)
    return i;
    else if(nums[i]>target)
    return i;
    }
    return nums.length;
    }


  • 2
    S

    can anyone explain why it returns low? when target is not found?


  • 1
    C

    @shaunzeng Because the consition(low<=high) The =.


  • 0
    Y

    @AmmsA why declaration of var 'mid' is in the while loop ,it may waste more time than declaration in the front?


  • 2
    H

  • 0
    J

    @codingXiaxw nice!


  • 0
    D
    # code block I'm a green hand
    class Solution(object):
        def searchInsert(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            for i in nums:
                if i >= target:
                    return nums.index(i)
            return len(nums)
    

Log in to reply
 

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