老师有时间方便的话，看下我自己实现的floor函数是否可行或者改进的地方。
来源：5-1 二分查找法（Binary Search）
qq_邪饿的小强_0
2018-04-03
/**
* 查找arr[l，r]的floor索引
* @param arr
* @param target
* @param l
* @param r
* @return
*/
public static int floor(Comparable[] arr, Comparable target,int l,int r){
if(l > r){
//没有相等的就返回左边的索引值
return r;
}
int i = l + (r - l)/2;
if(arr[i].compareTo(target) == 0){
//如果左边相等 索引左移动
while (i-1 >= l && arr[i-1].compareTo(arr[i]) == 0) i--;
return i;
}else if(arr[i].compareTo(target)<0){
l = i+1;
//如果右边相等 索引右移动
while (l+1 <= r && arr[l+1].compareTo(arr[l]) == 0) l++;
}else{
r = i-1;
//如果左边相等 索引左移动
while (r-1 >= l && arr[r-1].compareTo(arr[r]) == 0) r--;
}
return floor(arr,target,l,r);
}
1回答
-
liuyubobobo
2018-04-03
课程的官方Github提供了floor的实现，可以参考：）
课程官方github：https://github.com/liuyubobobo/Play-with-Algorithms
课程官方github提供的floor实现：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/05-Binary-Search-Tree/Course%20Code%20(C%2B%2B)/Optional-02-Floor-and-Ceil-in-Binary-Search/main.cpp
00
相似问题