Tìm kiếm trong một mảng được sắp xếp có kích thước không xác định trong C ++

Giả sử chúng ta có một mảng và được sắp xếp theo thứ tự tăng dần, chúng ta phải xác định một hàm để tìm kiếm mục tiêu theo nums. Nếu mục tiêu hiện diện, thì trả về chỉ mục của nó, ngược lại, trả về -1.

Kích thước mảng không được biết. Chúng ta chỉ có thể truy cập vào mảng bằng giao diện ArrayReader. Có một hàm get như ArrayReader.get (k), hàm này sẽ trả về phần tử của mảng ở chỉ số k.

Vì vậy, nếu đầu vào giống như mảng =[-1,0,3,5,9,12], target =9, thì đầu ra sẽ là 4 vì 9 tồn tại trong nums và chỉ số của nó là 4

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

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

• trong khi nhận được (cao) người đọc

  • thấp:=cao

  • cao =cao * 2

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

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

  • x:=get (giữa) người đọc

  • nếu x giống với target thì -

    • trở về giữa

  • nếu x> target, thì -

    • cao:=giữa - 1

  • Nếu không

    • thấp:=mid + 1

• trả về -1

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 ArrayReader{
private:
   vector<int> v;
public:
   ArrayReader(vector<int> &v){
      this->v = v;
   }
   int get(int i){
      return v[i];
   }
};
class Solution {
public:
   int search(ArrayReader& reader, int target) {
      int high = 1;
      int low = 0;
      while (reader.get(high) < target) {
         low = high;
         high <<= 1;
      }
      while (low <= high) {
         int mid = low + (high - low) / 2;
         int x = reader.get(mid);
         if (x == target)
            return mid;
         if (x > target) {
            high = mid - 1;
         }
         else
            low = mid + 1;
      }
      return -1;
   }
};
main(){
   Solution ob;
   vector<int> v = {-1,0,3,5,9,12};
   ArrayReader reader(v);
   cout<<(ob.search(reader, 9));
}

Đầu vào

{-1,0,3,5,9,12}, 9

Đầu ra

4