//個人學習筆記用
- 題目：
給定一個排序陣列和一個目標值，在陣列中找到目標值，并回傳其索引，如果目標值不存在于陣列中，回傳它將會被按順序插入的位置，
請必須使用時間復雜度為 O(log n) 的演算法，
參考題解--代碼隨想錄
-
暴力解法：
class Solution { public: int searchInsert(vector<int>& nums, int target) { for(int i = 0; i< nums.size();i++){ if (nums[i] >= target){ return i; } } return nums.size(); } }; //決議：他是要回傳位置，所以可以不用插入資料，直接回傳位置即可 -
二分解法
class Solution { public: int searchInsert(vector<int>& nums, int target) { if(nums.empty()) return 0; int left = 0; int right = nums.size() - 1; while(left <= right){ //int middle = (left + right)/2; int middle = left + ((right - left)/2); //左右變數一直在變化，那么要計算middle就要在回圈里面定義，即隨著left 、right的變化，middle也在變化 if(nums[middle] < target) left = middle + 1; else if(nums[middle] > target) right = middle -1; else return middle; } return right + 1; } }; //決議：他是要回傳位置，所以可以不用插入資料，直接回傳位置即可
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if(nums.empty())
return 0;
int left = 0;
int right = nums.size() - 1;
while(left <= right){
//int middle = (left + right)/2;
int middle = left + ((right - left)/2); //左右變數一直在變化，那么要計算middle就要在回圈里面定義，即隨著left 、right的變化，middle也在變化
if(nums[middle] < target)
left = middle + 1;
else if(nums[middle] > target)
right = middle -1;
else
return middle;
}
return right + 1;
}
};
//二分查找，left、right從兩側向目標值靠攏，直到left = right，再執行一次操作，
//無論執行哪一個，那么，right 一定會小于 left，那最后的目標值，應插入到right（最小值）+1的位置
//決議：他是要回傳位置，所以可以不用插入資料，直接回傳位置即可
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/554549.html
標籤：其他
上一篇：資料結構 in Golang：Hash Tables（哈希表）
下一篇：返回列表