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