Search Insert Position trong C++

Cho mảng đã sắp xếp và target, tìm chỉ số của target. Nếu không có, trả về chỉ số chèn để giữ mảng sắp xếp.

Ví dụ: [1,3,4,6,6], target=5 → index 3 (chèn giữa 4 và 6).

Giải thuật (Binary Search)

1. low=0, high=n-1.
2. Khi low ≤ high: mid = low + (high-low)/2.
3. Nếu A[mid] == target → return mid.
4. Nếu A[mid] > target → high = mid-1, pos = mid.
5. Ngược lại → low = mid+1, pos = mid+1.
6. Trả về pos.

Ví dụ triển khai C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int searchInsert(vector<int>& A, int target) {
        int n = A.size();
        if (n == 0) return 0;
        int low = 0, high = n - 1, pos = n;
        while (low <= high) {
            int 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;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,3,4,6,6};
    cout << ob.searchInsert(v, 5); // 3
    return 0;
}

Đầu vào / Đầu ra

Input: {1,3,4,6,6}, 5
Output: 3