ค้นหาตำแหน่งแทรกใน C ++

สมมติว่าเรามีอาร์เรย์ที่จัดเรียง arr และค่าเป้าหมาย เราต้องหาดัชนีเมื่อพบเป้าหมาย หากไม่มีอยู่ ให้ส่งคืนดัชนีในตำแหน่งที่ควรจะเป็นหากใส่เข้าไปตามลำดับ

ดังนั้น หากอินพุตเป็น [1,3,4,6,6] และเป้าหมาย =5 ผลลัพธ์จะเป็น 3 เนื่องจากเราสามารถแทรก 5 ที่ดัชนี 3 ดังนั้นอาร์เรย์จะเป็น [1,3 4,5,6,6]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้-

• n :=ขนาดของ A

• ถ้า n <1 แล้ว −

  • คืนค่า 0

• ต่ำ :=0, สูง :=n - 1

• ในขณะที่ต่ำ <=สูง ทำ -

  • กลาง :=ต่ำ + (สูง - ต่ำ) /2

  • ถ้า A[mid] เหมือนกับเป้าหมาย ดังนั้น −

    • คืนกลาง

  • มิฉะนั้นเมื่อ A[กลาง]> เป้าหมาย จากนั้น −

    • สูง :=กลาง - 1, ตำแหน่ง :=กลาง

  • อย่างอื่น

    • ต่ำ :=กลาง + 1, ตำแหน่ง :=กลาง + 1

• ตำแหน่งส่งคืน

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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