```
public class Solution {
public int searchInsert(int[] nums, int target) {
if (nums.length == 0) return 0;
if (nums.length == 1){
if (target > nums[0]) return 1;
return 0;
}
int pos = nums.length-1;
if (target > nums[nums.length-1]) return nums.length;
if (target <= nums[0]) return 0;
while(target < nums[pos]) pos = pos/2;
for (int i = pos; i < pos*2+1; i++) {
if (nums[i] >= target) return i;
}
return pos*2+1;
}
}
```