Tìm vị trí phần tử trong mảng vô hạn đã sắp xếp trong C++

Trong bài toán này, cho mảng chứa vô hạn số đã sắp xếp. Nhiệm vụ là tìm vị trí phần tử trong mảng vô hạn.

Ví dụ minh họa:

Đầu vào

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

Đầu ra

4

Phương pháp giải

Dùng tìm kiếm nhị phân (binary search) nhưng không biết endpoint. Sửa đổi thuật toán: fix start = 0, end = 1. Kiểm tra arr[end], nếu < key thì start = end, end *= 2. Khi arr[end] >= key, binary search trong đoạn [start, end].

Chương trình minh họa:

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

Kết quả

Element found! index = 5