Geek Answers Handbook

Faster than a binary search of an ordered list

is there an algorithm that is faster than binary search to search in sorted array values?

in my case, I have sorted values ​​(there can be any type values) in the array A, I need to return nif the value I was looking for is in the rangeA[n] and A[n+1]

+25
source share
10 answers

You can do better than O (log n) if the values ​​are integers, in which case the best worst-case execution time you can achieve, from the point of view of n, is O (sqrt (log n)). Otherwise, there is no way to beat O (log n) if there are no patterns in the input sequence. There are two approaches used to extract O (log n) in the case of integers.

y-fast , , - , . , . , O (log w), w - . , , (. ).

-, , , w ^ O (1) , O (log n/log w).

, log w = sqrt (log n), O (sqrt (log n)).

. 12 13 : http://courses.csail.mit.edu/6.851/spring07/lec.html

+32

, . , :

a[i] <= i <= a[i + 1]

:

a[i] - i <= 0 <= a[i + 1] - i

- . , , , , .

http://en.wikipedia.org/wiki/Root-finding_algorithm

+6

, , . , , . , , .

+5

. , , . , O (lg N), .

, . , , - , . . , - . , , , , , .

, , , . , (, ) , .

4 8 ( 2) , , , , -.

O (lg N).

+4

? . http://en.m.wikipedia.org/wiki/Exponential_search

k A n. Lookup A [2 ^ i] = 0, 1, 2,... k A., (), i.

int exponential_search(int A[], int key)
{
  // lower and upper bound for binary search
  int lower_bound = 0;
  int upper_bound = 1;

  // calculate lower and upper bound
  while (A[upper_bound] < key) {
    lower_bound = upper_bound;
   upper_bound = upper_bound * 2;
  }
  return binary_search(A, key, lower_bound, upper_bound);
}

O (log idx), idx - k A. ( stpes log idx). , algo O (log idx), k A , A. , , , .

n, , .

+2

-, O (1). , , , -, , . Re-bucketing - O (n), O (1). , .

+1

, , .

?

, , -, . . (, std::map, ) ? , / , , , /, , .

, - , , , , , , , , .

, , , , (, , -) 1 , , .

hth.

+1

"", , . , .

, , , . , , . ( , , ).

0

, - -, O (n + m), m - . , , .

... . , p , , , , , . 2 ^ p * lg (n), n - . O (2 ^ p), 2 ^ p/n, .

O (1)!

, , . . .

0

, O (log N), , O (log N).

, SIMD, .

, , , , O (1).

All of the above aspects are discussed with the test results in: Cannizzo, 2015, A quick and vector alternative to binary search in O (1), applicable to a wide area of ​​sorted arrays of floating-point numbers. The document comes with github source code .

0
source

More articles:


All Articles