Leetcode-35 —— Search Insert Position

Description

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

1 2	Input: [1,3,5,6], 5 Output: 2

Example 2:

1 2	Input: [1,3,5,6], 2 Output: 1

Example 3:

1 2	Input: [1,3,5,6], 7 Output: 4

Example 4:

1 2	Input: [1,3,5,6], 0 Output: 0

分析

在一个给定的有序数组中查找给定的值，如果找到返回该值在数组中的位置，否则返回该值所应该处于的位值。

给定的数组是有序的，而且已经假设没有重复的元素，显然二分查找是一种比较容易想到的解决方案。解决问题时，考虑以下 corner case,

给定的数组为空或 null
给定的 target 比数组最小值小
给定的 target 比数组最大值大

测试用例

根据分析给出的 corner case, 题目给出的测试用例已经基本覆盖，只需再加上给定数组为空的情况

1 2	Input: [], 2 Output: 0

程序设计

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

注意:

即便数组只有一个元素也要进行二分查找，因此 while 循环中的条件是 left <= right ，要有 =
如果进入 while 循环且查找失败，则 left 的值一定大于 right，此时 left 的位置正好代表查找元素所应该处于的位置，所以返回 left.
计算 mid 时候，考虑大数相加溢出，因此使用 mid = left + ((right - left) >> 1) 计算 mid 的值，其中 >> 是位运算，相当于 /，如果您不熟悉位运算可以改为如下表达式mid = left + (right - left)/2

代码提交后，运行时打败 100.00% 的提交，内存打败 98.22% 的提交，可以说近乎完美。