Thursday, January 30, 2014

LeetCode : Search insert position

It is easy to do by O(N)...

But this solution is by O(logN)

public class Solution {
    public int searchInsert(int[] A, int target) {

        int f=0;
        int l=A.length;
        int m;
        
        while(true)
        {
            m=(f+l)/2;
            if(m>0&&m<A.length)
            {    if(target>A[m-1]&&target<=A[m]) return m;}
            else if(m==0)
            {
                if(target<=A[m]) return m;
            }
            else
            {    if(target>A[m-1]) return m;}

            
            if(target>A[m])
                f=m+1;
            else if(target<A[m])
                l=m;
        }
    }
}

No comments:

Post a Comment