[数据结构与算法]35. 搜索插入位置

题目描述： 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。
示例1：
输入: [1,3,5,6], 5
输出: 2
示例2：
输入: [1,3,5,6], 2
输出: 1
示例3：
输入: [1,3,5,6], 7
输出: 4
示例4：
输入: [1,3,5,6], 0
输出: 0
来源： 力扣（LeetCode）
链接： https://leetcode-cn.com/problems/search-insert-position/
解决方案：
方法1：暴力破解法，直接使用一个for循环解决，时间复杂度为O(N).

	// 法一：暴力破解法
	public static int searchInsert(int[] nums, int target) {
		for (int i = 0; i < nums.length; i++) {
			// 分别处理如下三种情况
        	// 目标值在数组所有元素之前
       	 	// 目标值等于数组中某一个元素  
        	// 目标值插入数组中的位置 
			if (target <= nums[i]) {
				return i;
			}
		}
		// 目标值在数组所有元素之后的情况 
		return nums.length;
	}

方法2：二分查找法，如题描述，数组为排序数组，因此可以联想使用二分查找法解决，时间复杂度为O(logN).

// 法二：二分查找法
	public static int searchInsert(int[] nums, int target) {
		int left = 0, right = nums.length - 1;
		while (left <= right) {
			// left + (right + left) / 2 形式，防止溢出，效果等同于 (left + right) / 2
			int mid = left + (right - left) / 2;
			if (nums[mid] == target) {
				return mid;
			} else if (nums[mid] > target) {
				right = mid - 1;
			} else {
				left = mid + 1;
			}
		}
		// 分别处理如下四种情况
        // 目标值在数组所有元素之前  [0, -1]
        // 目标值等于数组中某一个元素  return middle;
        // 目标值插入数组中的位置 [left, right]，return  right + 1
        // 目标值在数组所有元素之后的情况 [left, right]， return right + 1
		return right + 1;
	}