【二分法】LeetCode-Search Insert Position
- 2020 年 3 月 29 日
- 筆記
前言
今天在LeetCode遇到一个这样的题目.
题目意思就是给一个排好序的数组和要寻找的数，若数组存在，返回它的index，否则返回它该插入的位置。
思考
拿到这个问题，哇，这不就是普通的二分法吗？那就刷刷的写下了二分法的代码：
func searchInsert(_ nums: [Int], _ target: Int) -> Int { var low = 0 var high = nums.count - 1 var mid = -1 while low <= high { mid = (high + low) / 2 if target == nums[mid] { return mid }else if target > nums[mid] { low = mid + 1 }else { high = mid - 1 } } return -1 }
以上代码是最原始的二分查找法，若存在返回对应的索引，不存在返回-1。而题目额外要求找不到，就返回要插入的位置。这时候我就纠结low，mid，high之间，究竟哪一个才是要插入的位置呢？想了半天没思绪，看了下答案，只需要将return -1改为return low就可以了。
疑惑
为什么是返回low，而不是返回high，或者是返回mid。所以我又搜了一下关于二分法的相关资料，看完这篇博客后，恍然大悟。
二分法有很多变种形式，例如查找最后一个等于或者小于key的元素等形式（可以去看该博客）。最后该博客，总结了二分法各形式变化，以下为该博客的结论：
1、首先确定返回的是left，还是right
- 跳出while (left <= right)循环条件是right < left，且right = left – 1。
- right和left一定是卡在"边界值"的左右两边
- 如果是比较值为key，查找小于等于（或者是小于）key的元素，则边界值就是等于key的所有元素的最左边那个，其实应该返回left。
例子
以数组{1, 2, 3, 3, 4, 5}为例，如果需要查找第一个等于或者小于3的元素下标，我们比较的key值是3，则最后left和right需要满足以下条件：
例子.png
我们比较的key值是3，所以此时我们需要返回left
2、判断出比较符号
int mid = (left + right) / 2; if (array[mid] ? key) { //... right = xxx; } else { // ... left = xxx; }
也就是这里的 if (array[mid] ? key) 中的判断符号，结合步骤1和给出的条件，如果是查找小于等于key的元素，则知道应该使用判断符号>=，因为是要返回left，所以如果array[mid]等于或者大于key，就应该使用>=，以下是完整代码
// 查找小于等于key的元素 int mid = (left + right) / 2; if (array[mid] >= key) { right = mid - 1; } else { left = mid + 1; }
为什么返回的是low
套用结论，high = low - 1
- target小于所有元素，插入的位置是0，high为-1，low=0才能跳出循环
- target大于所有元素，插入的位置的数组的长度count，high为count-1，low=count才能跳出循环
- target小于数组中某些元素，大于某些元素，问题就转化为查找第一个大于target的元素下标。根据结论，high和low总是在临界值的两边，那么就相当于 high-target-low，因此返回low
总上述三种情况，返回low都符合题目要求
总结
看似简单的二分法，如果换种提问方式，或许就绕进去出不来了。因此，在这里做这个总结，加深自己的理解
