問(wèn)題描述：
給定一個(gè)排序數(shù)組nums(無(wú)重復(fù)元素)與目標(biāo)值target，如果target在nums里 出現(xiàn)，則返回target所在下標(biāo)，如果target在nums里未出現(xiàn)，則返回target應(yīng)該 插入位置的數(shù)組下標(biāo)，使得將target插入數(shù)組nums后，數(shù)組仍有序。

例如：
數(shù)組 arr = [2,3,4,6]
target = 1時(shí)， 插入位置應(yīng)為 index = 0
target = 5時(shí)，插入位置應(yīng)為 index = 3
target = 3時(shí)，下標(biāo)就變?yōu)閕ndex = 1

這里我們分析：

1. 查找時(shí)我們?nèi)匀皇褂谜５亩植檎?#xff0c;關(guān)于二分查找的遞歸和非遞歸實(shí)現(xiàn)可以參考二分法：二分查找（遞歸+非遞歸）實(shí)現(xiàn)
2. 假如我們找到了target，那么index = mid
3. 如果arr[mid] > target且 (mid == 0 或者 arr[mid -1] < target)
   index = mid - 1
   這個(gè)就是將mid卡在一個(gè)范圍內(nèi)，比如[2,4,5,6]中查找3，arr[1] > 3但是arr[0] < 3
4. 如果arr[mid] < target 且(mid == arr.size() - 1 或者 arr[mid + 1] > target)
   這同樣時(shí)將mid卡在另一個(gè)上升區(qū)間，比如[2,3,4,6]中查找5,arr[2]<5,但是arr[3]>5
   此時(shí)index = mid + 1

綜上，我們可以寫(xiě)出如下實(shí)現(xiàn)過(guò)程

int find_part(std::vector<int> &arr, int target) {int begin = 0;int end = arr.size() - 1;int mid = (begin + end) / 2;int index = -1;while(index == -1) {if (arr[mid] == target) {index = mid; } else if (arr[mid] > target) {//左區(qū)間if (mid == 0 || target > arr[mid - 1]) {index = mid;//target比數(shù)組開(kāi)頭小，保證target是插入到了0}end = mid - 1; //縮小mid范圍}else if (arr [mid] < target) { //右區(qū)間if (mid == (arr.size() - 1) || target < arr[mid + 1]) {index = mid + 1;}begin = mid + 1;}mid = (begin + end) / 2;}return index;
}

測(cè)試代碼如下:

#include <iostream>
#include <vector>using namespace std;int find_part(std::vector<int> &arr, int target) {int begin = 0;int end = arr.size() - 1;int mid = (begin + end) / 2;int index = -1;while(index == -1) {if (arr[mid] == target) {index = mid;} else if (arr[mid] > target) {if (mid == 0 || target > arr[mid - 1]) {index = mid; //target比數(shù)組開(kāi)頭小，保證target是插入到了0}end = mid - 1;}else if (arr [mid] < target) {if (mid == (arr.size() - 1) || target < arr[mid + 1]) {index = mid + 1;}begin = mid + 1;}mid = (begin + end) / 2;}return index;
}
int main() {std::vector<int> arr1;int n;cin >> n;for (int i = 0;i < n; ++i) {int tmp;cin >> tmp;arr1.push_back(tmp);}int target;cin >> target;cout << find_part(arr1, target);return 0;
}

輸出如下:

#輸入
5
2 3 4 5 6
1
#輸出
0

總結(jié)

以上是生活随笔為你收集整理的二分法：search insert position 插入位置的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。