算法与数据结构(13)—— 二分查找(递归与非递归)
程序员文章站
2022-06-17 19:46:28
...
递归
private static int find(Comparable[] arr, int l, int r, Comparable target){
if(l > r) return -1;
int mid = (r-l)/2 + l;
if(arr[mid].compareTo(target) == 0)
return mid;
else if(arr[mid].compareTo(target) > 0)
return find(arr, l, mid-1, target);
else
return find(arr, mid+1, r, target);
}
public static int find(Comparable[] arr, Comparable target){
return find(arr, 0, arr.length-1, target);
}
非递归
public static int find(Comparable[] arr, Comparable target){
// 在arr[l...r]之中查找target
int l = 0, r = arr.length - 1;
while(l <= r){
int mid = (r - l)/2 + l;
if(arr[mid].compareTo(target) == 0){
return mid;
}else if(arr[mid].compareTo(target) > 0){
r = mid - 1;
}else if(arr[mid].compareTo(target) < 0){
l = mid + 1;
}
}
return -1;
}
上一篇: 算法-二分查找(非递归)