Struzik Search
这个就是姚院和Jon Bentley的搜索, 先用exponential的方法找到最近的搜索区域, 然后再用二叉搜索.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <bits/stdc++.h> using namespace std; int binarySearch(int a[], int l, int r, int key) { int m; while (l <= r) { m = l + (r - l) / 2; if (a[m] == key) { return m; } else if (a[m] > key) { r = m - 1; } else { l = m + 1; } } return -1; } int exponentialsearch(int a[], int size, int key) { if (a[0] == key) { return 0; } int i = 1; while (i < size && a[i] < key) { i = i * 2; } return binarySearch(a, i/2, min(i, size), key); } |