Tìm kiếm Chèn vị trí trong C ++

Giả sử chúng ta có một mảng được sắp xếp arr và một giá trị đích, chúng ta phải tìm chỉ mục khi mục tiêu được tìm thấy. Nếu không có, hãy trả về chỉ mục ở vị trí nếu nó được chèn theo thứ tự.

Vì vậy, nếu đầu vào là [1,3,4,6,6] và target =5, thì đầu ra sẽ là 3, vì chúng ta có thể chèn 5 vào chỉ mục 3, vì vậy mảng sẽ là [1,3, 4,5,6,6]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau−

• n:=kích thước của A

• nếu n <1, thì -

  • trả về 0

• thấp:=0, cao:=n - 1

• trong khi thấp <=cao, làm -

  • giữa:=low + (cao - thấp) / 2

  • nếu A [mid] giống với target, thì -

    • trở về giữa

  • ngược lại khi A [mid]> target thì -

    • cao:=mid - 1, pos:=mid

  • nếu không thì

    • thấp:=mid + 1, pos:=mid + 1

• trả về vị trí

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

{1,3,4,6,6},5

Đầu ra

3