# 面试算法：在未知长度的排序数组中进行快速查找

public class SearchingUnkownLengthSortedArray {

private int[] array = null;

public SearchingUnkownLengthSortedArray(int[] A) {
this.array = A;
}

private int binarySearch(int[] A, int k, int begin, int end) {
/*
* 在区间[begin, end]中进行二分查找，如果找到则返回下标，找不到则返回-1
*/
while (begin <= end) {
int m = (begin + end) / 2;
//如果访问A[m]出现异常，那么把end设置为m-1，然后继续执行二分查找
try {
if (A[m] == k) {
return m;
}

if (A[m] < k) {
begin = m + 1;
}

if (A[m] > k) {
end = m - 1;
}

}catch (ArrayIndexOutOfBoundsException e) {
System.out.println("mid point out of length: " + m);
end = m - 1;
}
}

return -1;
}

public int searchingWithUnknownLength(int k) {
/*
* 下标从0，1，2依次倍增，如果下标增加到2p时，访问越界，那么在[p, 2p]间进行二分查找
*/
if (this.array[0] == k) {
return 0;
}

if (this.array[0] > k) {
return -1;
}

int endKeeper = 1;
while (true) {
try {
if (this.array[endKeeper] < k) {
endKeeper = endKeeper << 1;
} else if (this.array[endKeeper] == k){
return endKeeper;
}else {
return this.binarySearch(this.array, k, 0, endKeeper);
}
}catch(ArrayIndexOutOfBoundsException e) {
System.out.println("index out of array length: " + endKeeper);
return this.binarySearch(this.array, k, endKeeper >> 1, endKeeper);
}
}

}

}

public class Searching {
public static void main(String[] args) {
int A[] = {1, 2, 3, 4 , 5, 6, 7, 8, 9 , 10};
SearchingUnkownLengthSortedArray su = new SearchingUnkownLengthSortedArray(A);
int idx = su.searchingWithUnknownLength(10);
if (idx != -1) {
System.out.println("The given key is at index of " + idx);
} else {
System.out.println("The array do not contain the given key");
}
}
}

131 篇文章39 人订阅

0 条评论

## 相关文章

2749

1112

1962

1161

1844

4492

1173

### Java程序员们最常犯的10个错误

Arrays.asList()会返回一个ArrayList对象，ArrayList类是Arrays的一个私有静态类，而不是java.util.ArrayList...

571

2306

1845