LeetCode 35 - Search Insertion Position

作者 QIFAN 日期 2017-01-14
LeetCode 35 - Search Insertion Position

原题链接: 35. Search Insertion Position


题干

给定一个排序数组 nums 和一个目标值 target ,返回该 target 在数组中的位置。若没有找到,则返回可以插入 target 而保持数组仍然有序的位置。

假设没有重复元素。

思路

这个还是用二分查找。时间复杂度为 $O(logn)$ 。

与 binary search 不同的是,在每次缩小范围的同时记录下当前搜索范围内可以插入的最小的位置,这样就减少最后没找到还要回去找一遍的时间。设最小插入位置为 x 。

  • nums[mid] == target 。返回 mid 。
  • nums[mid] > target 。x = min(mid, x)。并搜索 (lo, mid - 1) 。
  • nums[mid] < target 。x = min(hi + 1, x) 。并搜索 (mid + 1, hi) 。

代码:

public int searchInsert(int[] nums, int target) {
return binarySearch(nums, target, nums.length, 0, nums.length - 1);
}
private int binarySearch(int[] nums, int target, int toInsert, int lo, int hi) {
// base case
if (lo > hi) {
return toInsert;
}
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] > target) {
toInsert = Math.min(mid, toInsert);
return binarySearch(nums, target, toInsert, lo, mid - 1);
} else {
// 是 hi + 1 而不是 hi 。因为并不知道 nums[hi] 与 target 是否相等。
toInsert = Math.min(hi + 1, toInsert);
return binarySearch(nums, target, toInsert, mid + 1, hi);
}
}