搜索插入位置

import java.util.*;


public class Solution {
    int index = -1;

    /**
     * 
     * @param A int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int searchInsert (int[] nums, int target) {
        // write code here
        searchHelper(nums, 0, nums.length - 1, target);
		return index;
    }
    public void searchHelper(int[] nums, int left, int right, int target) {
		if (left > right) {
			// 如果没有该元素，则返回left的值（自己画一下就知道了）
			index = left;
			return;
		}
		int mid = (right - left) / 2 + left;
		if (nums[mid] == target) {
			index = mid;
			return;
		} else if (nums[mid] < target) {
			searchHelper(nums, mid + 1, right, target);
		} else {
			searchHelper(nums, left, mid - 1, target);
		}
	}
}

解法一：
public class Solution {
    public int searchInsert(int[] A, int target) {
//循环遍历数组，若目标数target小于等于A[i],则返回下标i，若循环能走完，则目标数target比数组最后一个数还要大，直接返回len+1
        int len= A.length;
        for(int i = 0; i < len; i++){
            if(A[i] >= target){
                return i;
            }
        }
        return len;
    }
}
解法二：
public class Solution {
    public int searchInsert(int[] A, int target) {
        //二分法查找
        int low = 0;
        int high = A.length - 1;
        while(low <= high){
            int mid = (low + high)/2;
            if(A[mid] == target)
                return mid;
            else if(A[mid] < target)
                low = mid + 1;
            else
                high = mid - 1;
        }
        return low;
    }
}

二分查找法，最后对low下标的值做个判断，如果其大于等于target，则target插入在low下标，否则插入在low+1位置。

public class Solution {
    public int searchInsert(int[] A, int target) {
        if (A == null || A.length == 0)
            return 0;
        int low = 0;
        int high = A.length-1;
        int mid;
        while (low < high) {
            mid = (low + high) / 2;
            if (target == A[mid])
                return mid;
            if (target < A[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }
        return (A[low] >= target) ? low : low + 1;
    }
}

public class Solution {
    public int searchInsert(int[] A, int target) {
        int left = 0;
        int right = A.length-1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(target == A[mid])
                return mid;
            if(target > A[mid])
                left = mid + 1;
            else
                right = mid -1;
        }
        return left;
    }
}

public class Solution {
    public int searchInsert(int[] A, int target) {
        // 二分查找
		int low = 0;
		int high = A.length - 1;
		while (low <= high) {
			int mid = (low + high) / 2;
			if(A[mid] == target) return mid;
			else if(A[mid] < target) low = mid + 1;
			else high = mid - 1;
		}
        // 没找到返回low,即插入位置
		return low;
	}
}

 public int searchInsert(int[] A, int target) { int low = 0, high = A.length-1; while(low<=high){ int mid = (low+high)/2; if(A[mid] == target) return mid; else if(A[mid] > target) high = mid-1; else low = mid+1;
        } return low;
    }