binary search

class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0) return 0;

        int n = nums.length;
        int left = 0, right = n - 1;

        while (left + 1 < right){
            int mid = left + (right - left) / 2;

            if (nums[mid] < target){
                left = mid;
            }
            else if (nums[mid] > target){
                right = mid;
            }
            else{
                return mid;
            }
        }

        if (nums[left] >= target){
            return left;
        }
        else if (nums[right] >= target){
            return right;
        }

        return n;
    }
}