Why my binary search is time limit exceeds..please


  • 0
    C
    int searchInsert(int A[], int n, int target) { //binary search
    int iLow    = 0;
    int iHigh   = n-1;
    while (iLow < iHigh) {
        // Take the average as the test value
        int iCheck = ((iLow + iHigh) >> 1);
        if (A[iCheck] > target) {
            iHigh   = iCheck;
        } else {
            iLow    = iCheck;
        }
    }
    return (A[iLow] < target)?iLow+1:iLow;
    }
    

    while this piece with a minor change with the iHigh variable is accepted.

    int searchInsert(int A[], int n, int target) { //binary search
    int iLow    = 0;
    int iHigh   = n;
    while (iLow < iHigh - 1) {
        // Take the average as the test value
        int iCheck = ((iLow + iHigh) >> 1);
        if (A[iCheck] > target) {
            iHigh   = iCheck;
        } else {
            iLow    = iCheck;
        }
    }
    return (A[iLow] < target)?iLow+1:iLow;
    }

  • 0
    S

    That 'minor' change is critical to your code. It is because in your binary search, the updated lower (upper) bound is set to the mid point, instead of ONE BEYOND the mid point. Think about a sequence of only two elements:

    [1 2]

    Initially, iLow = 0, iHigh = 1, and iCheck = 0. if A[iCheck] (A[0]) > target, then iLow will be set to 0 (without change). As a result, the loop will never be terminated.


  • 0
    C

    thanks man, you're totally right, I should start think it through from the simplest case.


  • 0
    A

    what about array A[1,2] and target is 3?? i think it will go to infinite loop... becoz
    ilow = 0,ihigh = 1,icheck = 0 and A[icheck]<target so ilow = icheck and while loop never get terminated..

    also for array A[1,2,3,4] suppose target is 5 your code will give the index 3 as the final answer.. How it accepted i am not getting.


  • 0
    C

    the 2nd piece is the one that has been accepted.


Log in to reply
 

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