Finding an index in a sorted array

Question

Given a sorted array A[1...n] of keys, and another key, x, stored in A, show how to find the index, k, so that A[k] = x in time O(log(k)).

I know that a binary search on a sorted array would be completed in O(logn), on average, but what would be the best way to show a run time of O(logk), as described above, for a sorted array?
I appreciate any help.

Are your keys arbitrary values, or are they specifically integers? — templatetypedef
– templatetypedef, Commented Feb 14, 2014 at 22:31
I don't get the O(logk).. what does the k have to do with the O() complexity? k is just the value of the index, right? If that x is at index 0 should I complete it in O(log0) ? — Marco A.
– Marco A., Commented Feb 14, 2014 at 22:33
@DavidKernin That's precisely what O(log k) is saying: Logarithmic in k, and hence (very slowly) growing as k grows. — user395760
– user395760, Commented Feb 14, 2014 at 22:37

Warren Dew · Accepted Answer · 2014-02-14 22:33:22Z

6

Do an exponential search, starting with index m=1 then doubling m each time, until the array element at m is greater than x. Then, do the normal binary search on the subset of the array below the final m.

answered Feb 14, 2014 at 22:33

Warren Dew

8,9383 gold badges34 silver badges44 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Thomas W Over a year ago

Yep, something like this.

Derrek Whistle Over a year ago

@user2580516 What is the reasoning behind doing an exponential search first?

user395760 Over a year ago

@DerrekWhistle Independence from the total number of items. The exponential search gives you an upper bound for k that is off by at most a factor of 2, so you can do binary search on a range of length O(k) regardless of how much larger n might be.

Warren Dew Over a year ago

@DerrekWhistle What delnan says. Basically an O(log k) algorithm is only useful if the searches are almost always for an item very close to the beginning of the list. The exponential search will limit the search space to the beginning of the list, avoiding a binary search of the whole list. If you think about the case where the target item is almost always the first item in the list, this will make more sense, I think.

Derrek Whistle Over a year ago

I see. Thank you both for the explanations.

Thomas W · Accepted Answer · 2014-02-14 22:35:50Z

0

Binary search giving O(log N) is the standard approach. I'm not sure if O(log k) is a misprint, a semi-equivalence, or suggests "biasing" the search towards the low end o the range.

Maybe a binary search using a non-halfway midpoint.. since differential of log is log, perhaps using log() function to choose a midpoint at each iteration?

answered Feb 14, 2014 at 22:35

Thomas W

14.2k4 gold badges64 silver badges77 bronze badges

Collectives™ on Stack Overflow

Finding an index in a sorted array

2 Answers 2

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related