Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stdlib.h>
- #include <time.h>
- #include <algorithm>
- using namespace std;
- int interpolatingSearch (int a[], int n, int key) {
- //изначально устанавливаем нижний индекс на начало массива,
- //а верний на конец массива
- int lo = 0;
- int hi = n - 1;
- int mid = -1;
- int index = -1;
- while(lo <= hi) {
- mid = lo + (((double)(hi - lo) / (a[hi] - a[lo])) * (key - a[lo]));
- if(a[mid] == key) {index = mid; break;}
- else {
- if(a[mid] < key) {
- // если значение в ячейке с индексом mid меньше, то смещаем нижнюю границу
- lo = mid + 1;
- } else {
- //в случае, если значение больше, то смещаем верхнюю границу
- hi = mid - 1;
- }
- }
- }
- return index;
- }
- int main() {
- srand(time(NULL));
- int n;
- cin >> n;
- int *a = new int[n];
- for (int i = 0; i < n; i++) a[i] = rand() % 50;
- sort(a, a + n);
- for (int i = 0; i < n; i++) cout << a[i] << " ";
- cout << endl;
- int key;
- cin >> key;
- cout << "index " << interpolatingSearch(a, n, key) << endl;
- delete [] a;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement