Faster than binary search for ordered list

c++ arrays algorithm search binary-search
uray picture uray · Oct 30, 2010 · Viewed 26.7k times · Source

is there an algorithm that is faster than binary search, for searching in sorted values of array?

in my case, I have a sorted values (could be any type values) in an A array, I need to return n if the value I was looking is in range of A[n] and A[n+1]

Answer

jonderry picture jonderry · Oct 30, 2010

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

First, you can use y-fast trees which work by storing in a hash table all prefixes for which you are storing at least one integer with that prefix. This enables you to perform a binary search to find the length of the longest matching prefix. This enables you to find the successor of an element for which you are searching in time O(log w) where w is the number of bits in a word. There are some details to work though to make this work and use only linear space, but they aren't too bad (see the link below).

Second, you can use fusion trees, which use bit tricks to enable you to perform w^O(1) comparisons in just a constant number of instructions, yielding a running time of O(log n / log w).

The optimum tradeoff between these two data structures occurs when log w = sqrt(log n), giving a running time of O(sqrt(log n)).

For details on the above, see lectures 12 and 13 of Erik Demaine's course: http://courses.csail.mit.edu/6.851/spring07/lec.html

Related questions

Searching in a sorted and rotated array

While preparing for an interview I stumbled upon this interesting question: You've been given an array that is sorted and then rotated. For example: Let arr = [1,2,3,4,5], which is sorted Rotate it twice to the right to give [4,5,1,2,3]. Now how best …

Read More
What is the safe way to fill multidimensional array using std::fill?

Here is what I am using: class something { char flags[26][80]; } a; std::fill(&a.flags[0][0], &a.flags[0][0] + 26 * 80, 0); (Update: I should have made it clear earlier that I am using this inside a class.)

Read More
Divide array into k contiguos partitions such that sum of maximum partition is minimum

Here maximum sum subset is one of k subsets that give maximum sum e.g: arr = [10,5,3,7] and k = 2 possible ways to divide arr in k subsets is {10,[5,3,7]},{[10,5],[3,7},{[10,5,3],7} and {[10,5],[3,7} is the optimal one. Edit: it is equivalent of https://www.codechef.…

Read More