二分法：search insert position 插入位置

問題描述：

給定一個排序數組nums(無重複元素)與目标值target，如果target在nums裡 出現，則傳回target所在下标，如果target在nums裡未出現，則傳回target應該 插入位置的數組下标，使得将target插入數組nums後，數組仍有序。

例如：

數組 arr = [2,3,4,6]

target = 1時， 插入位置應為 index = 0

target = 5時，插入位置應為 index = 3

target = 3時，下标就變為index = 1

這裡我們分析：

1. 查找時我們仍然使用正常的二分查找，關于二分查找的遞歸和非遞歸實作可以參考​​二分法：二分查找（遞歸+非遞歸）實作​​
2. 假如我們找到了target，那麼index = mid

3. 如果arr[mid] > target且 (mid == 0 或者 arr[mid -1] < target)

   index = mid - 1

   這個就是将mid卡在一個範圍内，比如[2,4,5,6]中查找3，arr[1] > 3但是arr[0] < 3

4. 如果arr[mid] < target 且(mid == arr.size() - 1 或者 arr[mid + 1] > target)

   這同樣時将mid卡在另一個上升區間，比如[2,3,4,6]中查找5,arr[2]<5,但是arr[3]>5

   此時index = mid + 1

綜上，我們可以寫出如下實作過程

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比數組開頭小，保證target是插入到了0
      }
      end = mid - 1; //縮小mid範圍
    }
     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;
}      

#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比數組開頭小，保證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