二分法有多少种写法都不重要，
重要的是要会写一种对的。
首先有几个数字要注意
中位数有两个，
常用的是下位中位数，通用的写法如下，语言int经常自动向下取整，
median = (length - 1) / 2
指针的区间当然可以开区间，也可以闭区间，也可以半开半闭。但老老实实两头取闭区间总是不会错。上面的中位数，转换成两头闭区间 [low,high] 就变成下面这样：
median = low + (high - low) / 2
这里还有个常见的坑，不要图快用加法，会溢出，
median = ( low + high ) / 2 // OVERFLOW
另外一个关键点是“终结条件”。
不要以 low == high 做终结条件。会被跳过的，
if (low == high) { return (nums[low] >= target)? low : ++low; }
不相信在 [1, 5] 里找 0 试试？
正确的终结条件是：
low > high
也就是搜索空间为空。
满足终结条件以后，返回值完全不需要纠结，直接返回低位 low。
因为回过头去放慢镜头，二分查找的过程就是一个 维护 low 的过程：
low从0起始。只在中位数遇到确定小于目标数时才前进，并且永不后退。low一直在朝着第一个目标数的位置在逼近。知道最终到达。
至于高位 high，就放心大胆地缩小目标数组的空间吧。
所以最后的代码非常简单，
public int binarySearch(int[] nums, int target) { int low = 0, high = nums.length-1; while (low <= high) { int mid = low + (high - low) / 2; if (nums[mid] < target) { low = mid + 1; } if (nums[mid] > target) { high = mid - 1; } if (nums[mid] == target) { return mid; } } return low; }
递归版也一样简单，
public int binarySearchRecur(int[] nums, int target, int low, int high) { if (low > high) { return low; } //base case int mid = low + (high - low) / 2; if (nums[mid] > target) { return binarySearchRecur(nums,target,low,mid-1); } else if (nums[mid] < target) { return binarySearchRecur(nums,target,mid+1,high); } else { return mid; } }
但上面的代码能正常工作，有一个前提条件：
元素空间没有重复值
推广到有重复元素的空间，二分查找问题就变成：
寻找元素第一次出现的位置。
也可以变相理解成另一个问题，对应C++的 lower_bound() 函数
寻找第一个大于等于目标值的元素位置。
但只要掌握了上面说的二分查找的心法，代码反而更简单，
public int firstOccurrence(int[] nums, int target) { int low = 0, high = nums.length-1; while (low <= high) { int mid = low + (high - low) / 2; if (nums[mid] < target) { low = mid + 1; } if (nums[mid] >= target) { high = mid - 1; } } return low; }
翻译成递归版也是一样，
public int firstOccurrenceRecur(int[] nums, int target, int low, int high) { if (low > high) { return low; } int mid = low + (high - low) / 2; if (nums[mid] < target) { return firstOccurrenceRecur(nums,target,mid + 1,high); } else { return firstOccurrenceRecur(nums,target,low,mid-1); } }
以上代码均通过leetcode测试。标准银弹。每天早起写一遍，锻炼肌肉。
最后想说，不要怕二分查找难写，边界情况复杂。实际情况是，你觉得烦躁，大牛也曾经因为这些烦躁过。一些臭名昭著的问题下面，经常是各种大牛的评论（恶心，变态，F***，等等）。而且这并不考验什么逻辑能力，只是仔细的推演罢了。拿个笔出来写一写，算一算不丢人。很多问题彻底搞清楚以后，经常就是豁然开朗，然后以后妥妥举一反三。以上。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。