CODEWITHSUNDEEP
arraysperformancealgorithmbig-o
Derrek Whistle
Derrek Whistle

Reputation: 711

Finding an index in a sorted array

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.

Upvotes: 2

Views: 253

Answers (2)

Thomas W
Thomas W

Reputation: 14154

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?

Upvotes: 0

Warren Dew
Warren Dew

Reputation: 8938

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.

Upvotes: 6

Related Questions