1. 題目
1.1 英文題目
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
1.2 中文題目
給定一個排序陣列和一個目標值，在陣列中找到目標值，并回傳其索引，如果目標值不存在于陣列中，回傳它將會被按順序插入的位置，
你可以假設陣列中無重復元素，
1.3輸入輸出
| 輸入 | 輸出 |
|---|---|
| nums = [1,3,5,6], target = 5 | 2 |
| nums = [1,3,5,6], target = 2 | 1 |
| nums = [1,3,5,6], target = 7 | 4 |
| nums = [1,3,5,6], target = 0 | 0 |
| nums = [1], target = 0 | 0 |
1.4 約束條件
- 1 <= nums.length <= 104
- -104 <= nums[i] <= 104
- nums contains distinct values sorted in ascending order.
- -104 <= target <= 104
2. 實驗平臺
IDE：VS2019
IDE版本：16.10.1
語言：c++11
3. 程式
3.1 測驗程式
#include "Solution.h"
#include <vector> // std::vector
#include<iostream> // std::cout
using namespace std;
// 主程式
void main()
{
// // 輸入
vector<int> nums = { 1,3,5,6 };
int val = 4;
Solution solution; // 實體化Solution
int k = solution.searchInsert(nums, val); // 主功能
// 輸出
cout << k << endl;
}
3.2 功能程式
3.2.1 最佳程式
（1）代碼
#pragma once
#include<vector> // std::vector
using namespace std;
//主功能（二分法+遞回）
class Solution
{
public:
int searchInsert(vector<int>& nums, int target)
{
int low = 0, high = nums.size()-1;
while(low<=high)
{
int mid = low + (high - low)/2;
if(target == nums[mid])
return mid;
else if(target>nums[mid])
low = mid+1;
else
high = mid-1;
}
return low;
}
};
此程式參考：https://blog.csdn.net/lym940928/article/details/79893316
（2）解讀
使用的是二分查找法，當while回圈完成時，說明沒有找到對應的數字，此時low > high，即low = high+1，因為數字樹位于[low, hight+1]中的，也即位于[low,low]之中，因此回傳low，即為target的最后的位置，
3.2.2 自寫程式
（1）代碼
#pragma once
#include<vector> // std::vector
using namespace std;
//主功能（二分法+遞回）
class Solution
{
public:
int searchInsert(vector<int>& nums, int target)
{
if (target <= nums[0]) return 0; // 如果目標值比陣列第一個元素還小，則回傳0
else
return func(nums, target, 0, nums.size()); // 運行主要函式
}
int func(vector<int>& nums, int target, int left, int right)
{
int min = 0;
if (right - left <= 1) return right;
else
{
int mid = (left + right) / 2;
if (nums[mid] > target)
{
right = mid;
return func(nums, target, left, right); // 遞回
}
else if (nums[mid] < target)
{
left = mid;
return func(nums, target, left, right);
}
else
return mid;
}
}
};
（2）思路
由約束條件一可知陣列不為空陣列，由約束條件三知陣列里的元素是按照升序排列的，也就是說不用考慮降序排列的情況，另外由題目中要求時間復雜度為O(log n)，可以聯想到是用二分法進行求解，二分法的程序中還用到了遞回的思想，
4. 相關知識
（1） 報錯：error: non-void function does not return a value in all control paths
這個錯誤在VS2019中沒有報，但是在Leetcode那里卻報錯了，當時挺蒙蔽的，后來查找資料才知道，原來是自己我if...else if...else if...else...里前幾個沒有return，也就是說有些情況沒有回傳值，考慮不周全，
這個可以參考：https://blog.csdn.net/pikaqiu123321123/article/details/114580378
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/288415.html
標籤：C++