C++:two binary search solutions


  • 1
    K

    I have two binary search solutions and they are both correct. Can anyone help me tell the difference and use the loop invariant to justify them

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

Log in to reply
 

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