Sorted Search, No Size: You are given an array-like data structure Listy which lacks a sizemethod. It does, however, have an elementAt(i) method that returns the element at index i in O(1) time. If i is beyond the bounds of the data structure, it returns -1. (For this reason, the data structure only supports positive integers.) Given a Listy which contains sorted, positive integers, find the index at which an element x occurs. If x occurs multiple times, you may return any index.
Hints: #320, #337, #348
解法1
Listy没有提供size方法，所以没有办法用二分查找。那么问题的关键是否在于如何知道它的size，知道之后就可以用二分查找。
是否可以这样呢，尝试在1、2、4、8、16、……的位置elementAt(i)，如果返回-1，那么就在前一个试探点到当前试探点之间的位置用二分找到elementAt(i) != -1 && elementAt(i + 1) == -1的点，从而知道它的size。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
public int getSize(Listy list) {
if (list.elementAt(0) == -1) {
return 0;
}
return getSize(list, 1, 1);
}
public int getSize(Listy list, int curr, int prev) {
if (list.elementAt(curr) == -1) {
return getSizeBinary(list, prev, curr - 1);
}
return getSize(list, curr * 2, curr);
}
public int getSizeBinary(Listy list, int start, int end) {
int mid = (start + end) / 2;
if (list.elementAt(mid) == 1 && list.elementAt(mid + 1) == -1) {
return mid - 1;
}
if (list.elementAt(mid) == -1) {
return getSizeBinary(list, start, mid - 1;)
}
return getSizeBinary(list, mid + 1, end);
}
|
查找Listy长度的时间复杂度：
- 最坏情况下，我们要试探logn次，并且在最后一段里也就是在n/2的长度里二分查找size。那也就是说复杂度是：O(logn + log(n/2))，也就是O(logn)
解法2（更好）
我们可以不要精确知道size，只需要知道n大概在哪个范围内。比如我们可以在1、2、4、8、……范围内试探，看一旦发现Listy.elementAt(i) > n，那么就知道n可能在[i / 2, i]这个范围内。当然，如果Listy.elementAt(i) == -1，也意味着n可能在[i / 2, i]这个范围内。
然后对这个返回做二分查找，二分的时候要注意，可以把-1认为是无限大。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public int search(Listy list, int n) {
int index = 1;
while (list.elementAt(index) != -1 && list.elementAt(index) < n) {
index = index * 2;
}
return binarySearch(list, n, index / 2, index);
}
private int binarySearch(Listy list, int n, int start, int end) {
if (start > end) {
return -1;
}
int mid = (start + end) / 2;
int midVal = list.elementAt(mid);
if (midVal == n) {
return mid;
}
if (midVal > n || midVal == -1) {
return binarySearch(list, n, start, mid - 1);
}
return binarySearch(list, n mid + 1, end);
}
|
评论