資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式編寫
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究搜尋在 C++ 中插入的位置
假設我們有一個已排序的陣列 arr 和一個目標值，我們必須在找到目標值時找到其索引。如果未找到，則返回將其按順序插入時的索引。
因此，如果輸入像 [1,3,4,6,6]，而目標值為 5，那麼輸出將是 3，因為我們可以在索引 3 處插入 5，因此陣列將變為 [1,3,4,5,6,6]
要解決此問題，我們將按照以下步驟操作：
n := A 的大小
如果 n < 1，則
返回 0
low := 0，high := n - 1
當 low <= high 時，執行以下操作：
mid := low + (high - low) /2
如果 A[mid] 與目標值相同時，則
返回 mid
否則，當 A[mid] > target 時，執行以下操作：
high := mid - 1，pos := mid
否則
low := mid + 1，pos := mid + 1
返回 pos
示例
為了更好地理解，讓我們看看以下實現：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int searchInsert(vector<int>& A, int target) {
int n = A.size();
if(n < 1) {
return 0;
}
int low = 0;
int high = n-1;
int mid;
int pos;
while(low <= high) {
mid = low + (high-low)/2;
if(A[mid] == target) {
return mid;
}
else if(A[mid] > target) {
high = mid - 1;
pos = mid;
}
else {
low = mid + 1;
pos = mid + 1;
}
}
return pos;
}
};
main(){
Solution ob;
vector<int&g; v = {1,3,4,6,6};
cout << (ob.searchInsert(v,5));
}輸入
{1,3,4,6,6},5輸出
3
更新於：10-6-2020
453 次瀏覽
廣告