แนวคิด
สมมติว่ามีอาร์เรย์ที่เรียงแล้ว arr และค่าเป้าหมาย ให้หาดัชนีเมื่อพบเป้าหมาย หากไม่มี ให้คืนค่าดัชนีที่จะวางได้ถ้าแทรกตามลำดับ
เช่น ถ้าอินพุตคือ [1,3,4,6,6] และ target = 5 ผลลัพธ์คือ 3 เพราะแทรก 5 ที่ดัชนี 3 อาร์เรย์จะเป็น [1,3,4,5,6,6]
วิธีแก้:
- n := ขนาด A
- ถ้า n < 1: คืนค่า 0
- low := 0, high := n - 1
- while low <= high:
- mid := low + (high - low) / 2
- ถ้า A[mid] เท่ากับ target: คืนค่า 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> v = {1,3,4,6,6};
cout << (ob.searchInsert(v,5));
}
อินพุต
{1,3,4,6,6},5
เอาต์พุต
3
