不是那种看别人现成的代码理解之后写出来,而是完全没听过,只给需求就能慢慢写出来这种。自己想达到的水平如下面贴出的。而自己现在处于:按自己思路写出的漏洞百出,改好这个 bug,又出新 bug 的水平。别说优雅了,下面这种难度的算法,完全给自己实现,都不能正确搞出来。。。
/**
* 二分查找法变种 floor, 在有序数组 arr 中, 查找 target
* 如果找到 target, 返回第一个 target 相应的索引 index
* 如果没有找到 target, 返回比 target 小的最大值相应的索引, 如果这个最大值有多个, 返回最大索引
* 如果这个 target 比整个数组的最小元素值还要小, 则不存在这个 target 的 floor 值, 返回-1
*
* @param arr
* @param target
* @return
*/
static int floor(Comparable[] arr, Comparable target) {
// 寻找比 target 小的最大索引
int l = -1, r = arr.length - 1;
while (l < r) {
// 使用向上取整避免死循环
int mid = l + (r - l + 1) / 2;
if (arr[mid].compareTo(target) >= 0) {
r = mid - 1;
} else {
l = mid;
}
}
assert l == r;
// 如果该索引+1 就是 target 本身, 该索引+1 即为返回值
if (l + 1 < arr.length && arr[l + 1] == target) {
return l + 1;
}
// 否则序列中无 target, 该索引即为返回值
return l;
}
这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。
V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。
V2EX is a community of developers, designers and creative people.