二分查找基础版（左闭右闭型） 需求：在有序 数组 $A$ 内，查找值 $target$
算法描述
前提
给定一个内含 $n$ 个元素的有序数组 $A$，满足 $A_{0}\leq A_{1}\leq A_{2}\leq \cdots \leq A_{n-1}$，一个待查值 $target$
1
设置 $i=0$(left)，$j=n-1$(right)
2
如果 $i \gt j$，结束查找，没找到
3
设置 $m = floor(\frac {i+j}{2})$ ，$m$ 为中间索引，$floor$ 是向下取整（$\leq \frac {i+j}{2}$ 的最小整数）
4
如果 $target < A_{m}$ 设置 $j = m - 1$，跳到第2步
5
如果 $A_{m} < target$ 设置 $i = m + 1$，跳到第2步
6
如果 $A_{m} = target$，结束查找，找到了
java 实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 public static int binarySearch (int [] a, int target) { int i = 0 , j = a.length - 1 ; while (i <= j) { int m = (i + j) >>> 1 ; if (target < a[m]) { j = m - 1 ; } else if (a[m] < target) { i = m + 1 ; } else { return m; } } return -1 ; }
$i,j$ 对应着搜索区间 $[0,a.length-1]$（注意是闭合的区间），$i<=j$ 意味着搜索区间内还有未比较的元素，$i,j$ 指向的元素也可能是比较的目标
思考：如果不加 $i=j$ 行不行？
回答：不行，因为这意味着 $i,j$ 指向的元素会漏过比较
$m$ 对应着中间位置，中间位置左边和右边的元素可能不相等（差一个），不会影响结果
如果某次未找到，那么缩小后的区间内不包含 $m$
二分查找改变版（左闭右开） 另一种写法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 public static int binarySearch (int [] a, int target) { int i = 0 , j = a.length; while (i < j) { int m = (i + j) >>> 1 ; if (target < a[m]) { j = m; } else if (a[m] < target) { i = m + 1 ; } else { return m; } } return -1 ; }
$i,j$ 对应着搜索区间 $[0,a.length)$（注意是左闭右开的区间），$i<j$ 意味着搜索区间内还有未比较的元素，$j$ 指向的一定不是 查找目标
思考：为啥这次不加 $i=j$ 的条件了？
回答：这回 $j$ 指向的不是查找目标，如果还加 $i=j$ 条件，就意味着 $j$ 指向的还会再次比较，找不到时，会死循环
如果某次要缩小右边界，那么 $j=m$，因为此时的 $m$ 已经不是 查找目标了
若只添加 $i=j$ 的条件但为修改 j = m - 1; -> j = m;运行以下代码时:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 int search = Solution.binarySearch(new int []{-1 , 0 , 3 , 5 , 9 , -1 }, 3 );public static int binarySearch (int [] a, int target) { int i = 0 , j = a.length; while (i < j) { int m = (i + j) >>> 1 ; if (target < a[m]) { j = m - 1 ; } else if (a[m] < target) { i = m + 1 ; } else { return m; } } return -1 ; }
循环次数
i
j
mid
target
a[m]
操作
1
0
6
3
3
0
target < a[m]
1
0
6
3
3
0
target < a[m]
2
0
2
1
3
5
a[m] < target
3
2
2
2
不满足i < j返回-1
二分查找性能 下面分析二分查找算法的性能
时间复杂度
最坏情况：$O(\log n)$
最好情况：如果待查找元素恰好在数组中央，只需要循环一次 $O(1)$
空间复杂度
需要常数个指针 $i,j,m$，因此额外占用的空间是 $O(1)$
二分查找平衡版 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public static int binarySearchBalance (int [] a, int target) { int i = 0 , j = a.length; while (1 < j - i) { int m = (i + j) >>> 1 ; if (target < a[m]) { j = m; } else if (a[m] < target) { i = m; } else { return m; } } return a[i] == target ? i : -1 ; }
上述代码中可以优化的是将目标元素小于中间元素的情况和目标元素大于中间元素的情况合并为一个条件。在除了目标元素小于中间元素的情况外，都将i更新为m。
思路是，如果目标元素不小于中间元素，那么它要么等于中间元素，要么大于中间元素。在这两种情况下，更新i为m仍然可以保持目标元素在搜索范围内。优化后：
1 2 3 4 5 6 7 8 9 10 11 12 public static int binarySearchBalance (int [] a, int target) { int i = 0 , j = a.length; while (1 < j - i) { int m = (i + j) >>> 1 ; if (target < a[m]) { j = m; } else { i = m; } } return (a[i] == target) ? i : -1 ; }
思想：
左闭右开的区间，$i$ 指向的可能是目标，而 $j$ 指向的不是目标
不奢望循环内通过 $m$ 找出目标, 缩小区间直至剩 1 个, 剩下的这个可能就是要找的（通过 $i$）
$j - i > 1$ 的含义是，在范围内待比较的元素个数 > 1
改变 $i$ 边界时，它指向的可能是目标，因此不能 $m+1$
循环内的平均比较次数减少了
时间复杂度 $\Theta(log(n))$
二分查找 Java 版 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 private static int binarySearch0 (int [] a, int fromIndex, int toIndex, int key) { int low = fromIndex; int high = toIndex - 1 ; while (low <= high) { int mid = (low + high) >>> 1 ; int midVal = a[mid]; if (midVal < key) low = mid + 1 ; else if (midVal > key) high = mid - 1 ; else return mid; } return -(low + 1 ); }
例如 $[1,3,5,6]$ 要插入 $2$ 那么就是找到一个位置，这个位置左侧元素都比它小
等循环结束，若没找到，low 左侧元素肯定都比 target 小，因此 low 即插入点
插入点取负是为了与找到情况区分
-1 是为了把索引 0 位置的插入点与找到的情况进行区分
若未找到 可以获取插入元素的位置(不是索引)即为-result+1
Leftmost 与 Rightmost 有时我们希望返回的是最左侧的重复元素，如果用 Basic 二分查找
对于数组 $[1, 2, 3, 4, 4, 5, 6, 7]$，查找元素4，结果是索引3
对于数组 $[1, 2, 4, 4, 4, 5, 6, 7]$，查找元素4，结果也是索引3，并不是最左侧的元素
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public static int binarySearchLeftmost1 (int [] a, int target) { int i = 0 , j = a.length - 1 ; int candidate = -1 ; while (i <= j) { int m = (i + j) >>> 1 ; if (target < a[m]) { j = m - 1 ; } else if (a[m] < target) { i = m + 1 ; } else { candidate = m; j = m - 1 ; } } return candidate; }
如果希望返回的是最右侧元素
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public static int binarySearchRightmost1 (int [] a, int target) { int i = 0 , j = a.length - 1 ; int candidate = -1 ; while (i <= j) { int m = (i + j) >>> 1 ; if (target < a[m]) { j = m - 1 ; } else if (a[m] < target) { i = m + 1 ; } else { candidate = m; i = m + 1 ; } } return candidate; }
应用
对于 Leftmost 与 Rightmost，可以返回一个比 -1 更有用的值
Leftmost 改为
1 2 3 4 5 6 7 8 9 10 11 12 public static int binarySearchLeftmost (int [] a, int target) { int i = 0 , j = a.length - 1 ; while (i <= j) { int m = (i + j) >>> 1 ; if (target <= a[m]) { j = m - 1 ; } else { i = m + 1 ; } } return i; }
leftmost 返回值的另一层含义：$\lt target$ 的元素个数
小于等于中间值，都要向左找
Rightmost 改为
1 2 3 4 5 6 7 8 9 10 11 12 public static int binarySearchRightmost (int [] a, int target) { int i = 0 , j = a.length - 1 ; while (i <= j) { int m = (i + j) >>> 1 ; if (target < a[m]) { j = m - 1 ; } else { i = m + 1 ; } } return i - 1 ; }
几个名词
范围查询 ：
查询 $x \lt 4$，$0 .. leftmost(4) - 1$
查询 $x \leq 4$，$0 .. rightmost(4)$
查询 $4 \lt x$，$rightmost(4) + 1 .. \infty $
查询 $4 \leq x$， $leftmost(4) .. \infty$
查询 $4 \leq x \leq 7$，$leftmost(4) .. rightmost(7)$
查询 $4 \lt x \lt 7$，$rightmost(4)+1 .. leftmost(7)-1$
求排名 ：$leftmost(target) + 1$
$target$ 可以不存在，如：$leftmost(5)+1 = 6$
$target$ 也可以存在，如：$leftmost(4)+1 = 3$
求前任（predecessor） ：$leftmost(target) - 1$
$leftmost(3) - 1 = 1$，前任 $a_1 = 2$
$leftmost(4) - 1 = 1$，前任 $a_1 = 2$
求后任（successor） ：$rightmost(target)+1$
$rightmost(5) + 1 = 5$，后任 $a_5 = 7$
$rightmost(4) + 1 = 5$，后任 $a_5 = 7$
求最近邻居 ：
完整代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 public class BinarySearch { public static int binarySearchBasic (int [] a, int target) { int i = 0 , j = a.length - 1 ; while (i <= j) { int m = (i + j) >>> 1 ; if (target < a[m]) { j = m - 1 ; } else if (a[m] < target) { i = m + 1 ; } else { return m; } } return -1 ; } public static int binarySearchAlternative (int [] a, int target) { int i = 0 , j = a.length; while (i < j) { int m = (i + j) >>> 1 ; if (target < a[m]) { j = m; } else if (a[m] < target) { i = m + 1 ; } else { return m; } } return -1 ; } public static int binarySearchBalance (int [] a, int target) { int i = 0 , j = a.length; while (1 < j - i) { int m = (i + j) >>> 1 ; if (target < a[m]) { j = m; } else { i = m; } } return (target == a[i]) ? i : -1 ; } public static int binarySearchLeftmost1 (int [] a, int target) { int i = 0 , j = a.length - 1 ; int candidate = -1 ; while (i <= j) { int m = (i + j) >>> 1 ; if (target < a[m]) { j = m - 1 ; } else if (a[m] < target) { i = m + 1 ; } else { candidate = m; j = m - 1 ; } } return candidate; } public static int binarySearchRightmost1 (int [] a, int target) { int i = 0 , j = a.length - 1 ; int candidate = -1 ; while (i <= j) { int m = (i + j) >>> 1 ; if (target < a[m]) { j = m - 1 ; } else if (a[m] < target) { i = m + 1 ; } else { candidate = m; i = m + 1 ; } } return candidate; } public static int binarySearchLeftmost2 (int [] a, int target) { int i = 0 , j = a.length - 1 ; while (i <= j) { int m = (i + j) >>> 1 ; if (target <= a[m]) { j = m - 1 ; } else { i = m + 1 ; } } return i; } public static int binarySearchRightmost2 (int [] a, int target) { int i = 0 , j = a.length - 1 ; while (i <= j) { int m = (i + j) >>> 1 ; if (target < a[m]) { j = m - 1 ; } else { i = m + 1 ; } } return i - 1 ; }
黑马程序员Java高级程序员必学的数据结构与算法
