二分查找的实现

Posted by mapoto4 on 2018-02-28

非递归方法

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int rank(int[] a, int key) {
int lo = 0;
int hi = a.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if(key < a[mid])
hi = mid - 1;
else if (key > a[mid])
lo = mid + 1;
else return mid;
}
return -1;
}

递归方法

1
2
3
4
5
6
7
8
9
public static int rank(int key, int[] a, int lo, int hi){
if(lo > hi) return -1;
int mid = lo + (hi - lo) / 2;
if(key < a[mid])
return rank(key, a, lo, mid - 1);
else if(key > a[mid])
return rank(key, a, mid + 1, hi);
else return mid;
}