前言
今天在LeetCode遇到一個這樣的題目.
題目意思就是給一個排好序的數(shù)組和要尋找的數(shù)，若數(shù)組存在透且，返回它的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)循環(huán)條件是right < left串稀，且right = left - 1。
- right和left一定是卡在"邊界值"的左右兩邊
- 如果是比較值為key爹凹，查找小于等于（或者是小于）key的元素厨诸，則邊界值就是等于key的所有元素的最左邊那個，其實應該返回left禾酱。
例子
以數(shù)組{1, 2, 3, 3, 4, 5}為例微酬，如果需要查找第一個等于或者小于3的元素下標，我們比較的key值是3颤陶，則最后left和right需要滿足以下條件：
我們比較的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才能跳出循環(huán)
- target大于所有元素，插入的位置的數(shù)組的長度count匈仗，high為count-1瓢剿，low=count才能跳出循環(huán)
- target小于數(shù)組中某些元素，大于某些元素悠轩，問題就轉化為查找第一個大于target的元素下標间狂。根據(jù)結論，high和low總是在臨界值的兩邊哗蜈，那么就相當于 high-target-low前标，因此返回low
總上述三種情況坠韩，返回low都符合題目要求
總結
看似簡單的二分法，如果換種提問方式炼列，或許就繞進去出不來了只搁。因此，在這里做這個總結俭尖，加深自己的理解
