Unbounded Searching Problem | Algorithms Notes

Unbounded Searching Problem | Algorithms Notes

Let A[n] be an array with n elements sorted in ascending order. It is simple to construct an O(n lg n) algorithm to find the position k in A[n] for a given value v. Assume that k is much less than n (i.e., k << n). Write an O(lg k) time algorithm to search for k.
(Note: you do not know the value of k in advance, only v is known)

Solution:

This is an application of binary search. Although we do not know k in advance, we can find the range of k. That is, find an integer i such that ≤ k < . Using linear search to find i costs O(i) = O(lg k). Then applying the binary search on the subarray ~ requires = O(i) = O(lg k) time, so the total time complexity is O(lg k).

This idea can also be generalized to higher dimension space.

解法：

這是一個二分搜尋法的應用。雖然事先不知道k的大小，但是可以利用演算法找出k的範圍，也就是找一個整數i使得 ≤ k < 。利用線性搜尋只需要花O(i) = O(lg k)的時間。接著只要在子陣列~中做二分搜尋即可，需要花 = O(i) = O(lg k)時間，所以整體時間還是O(lg k)。

Read full article from Unbounded Searching Problem | Algorithms Notes