My O(logn)solution with 16ms


  • 0
    I
    class Solution {
    public:
      int searchInsert(int A[], int n, int target) {
        int ret;
        if(target > A[n - 1])
            return  n;
        else if(target <= A[0])
            return 0;
    
        if(target == A[n/2])      //递归出口1,找到目标值
            ret = n/2;
        else if(n == 2)           //递归出口2,找不到目标值,则目标在两数之间
            ret = 1;
        else if(target < A[n/2])
            ret = searchInsert(A, n/2 + 1, target);
        else{
            ret = searchInsert(A + n/2, n - n/2, target);
            ret += n/2;
        }
        return ret;
      }
    };

Log in to reply
 

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