Tìm vị trí của một phần tử trong mảng số vô hạn được sắp xếp trong C ++

Trong bài toán này, chúng ta đưa ra một mảng bao gồm vô số số được sắp xếp. Nhiệm vụ của chúng ta là Tìm vị trí của một phần tử trong mảng có vô hạn được sắp xếp.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

arr[] = {2, 4, 6, 8, 9, 12, 14,17, ….}, ele = 9

Đầu ra

4

Giải thích

Phương pháp tiếp cận giải pháp

Để tìm kiếm các phần tử từ một mảng đã sắp xếp một cách hiệu quả, chúng tôi sẽ sử dụng phương pháp tìm kiếm nhị phân. Ở đây, duy nhất điểm kết thúc không được biết, chúng tôi sẽ sửa đổi thuật toán một chút.

Chúng tôi sẽ sửa con trỏ bắt đầu ở vị trí đầu tiên, sau đó đưa con trỏ cuối đến vị trí thứ hai. Sau đó, chúng tôi sẽ kiểm tra giá trị ở con trỏ cuối và gia tăng nó bằng cách nhân đôi nó nếu giá trị nhỏ hơn khóa và cập nhật điểm bắt đầu với vị trí cuối cùng của con trỏ kết thúc.

Khi giá trị vị trí cuối cùng lớn hơn phần tử được tìm thấy, chúng tôi sẽ tìm kiếm trong mảng con này bằng cách sử dụng tìm kiếm nhị phân.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#include<iostream>
using namespace std;
int binarySearch(int arr[], int start, int end, int ele) {
   if (end >= start) {
      int mid = start + (end - start)/2;
      if (arr[mid] == ele)
         return mid;
      if (arr[mid] > ele)
         return binarySearch(arr, start, mid-1, ele);
      return binarySearch(arr, mid+1, end, ele);
   }
   return -1;
}
int findPos(int arr[], int value) {
   int start = 0, end = 1;
   while (arr[end] < value) {
      start = end;
      end = 2*end;
   }
   return binarySearch(arr, start, end, value);
}
int main(){
   int arr[] = {1, 2, 4, 6, 8, 9, 12, 14, 17, 21, 45};
   int index = findPos(arr, 9);
   if (index == -1)
      cout<<"Element not found!";
   else
      cout<<"Element found! index = "<<index;
   return 0;
}

Đầu ra

Element found! index = 5