初识算法——二分查找

1.概念

二分查找算法也称折半查找，是一种非常高效的工作于有序数组的查找算法。

需求：在有序数组 $A$ 内，查找值 $target$

• 如果找到返回索引
• 如果找不到返回 $-1$

前提	给定一个内含 $n$ 个元素的有序数组 $A$，满足 $A_0\le A_1\le A_2\le \cdots \le A_{n-1}$，一个待查值 $target$
1	设置 $i=0$，$j=n-1$
2	如果 $i>j$，结束查找，没找到
3	设置 $m=floor(\frac{i+j}{2})$ ，$m$ 为中间索引，$floor$ 是向下取整（$\le \frac{i+j}{2}$ 的最小整数）
4	如果 $target<A_m$ 设置 $j=m-1$，跳到第2步
5	如果 $A_m<target$ 设置 $i=m+1$，跳到第2步
6	如果 $A_m=target$，结束查找，找到了

2.基础版

public static int binarySearch(int[] arr, int target) {int min = 0, max = arr.length - 1;while (min <= max) {int mid = (max + min) >>> 1;//无符号右移int midVal = arr[mid];if (target < midVal) {max = mid - 1;} else if (midVal < target) {min = mid + 1;} else {return mid;}}return -1;
}

3.改动版

public static int binarySearch(int[] arr, int target) {int min = 0, max = arr.length;while (min < max) {int mid = (max + min) >>> 1;//无符号右移int midVal = arr[mid];if (target < midVal) {max = mid;} else if (midVal < target) {min = mid + 1;} else {return mid;}}return -1;
}

4.衡量算法的好坏

对比线性查找

for (int i = 0; i < arr.length; i++) {if(arr[i] == target){return i;}
}
return -1;

事前分析法

图形计算器

计算机科学中，时间复杂度是用来衡量：一个算法的执行，随数据规模增大，而增长的时间成本

• 不依赖于环境因素

如何表示时间复杂度呢？

• 假设算法要处理的数据规模是 $n$，代码总的执行行数用函数 $f(n)$ 来表示，例如：

  • 线性查找算法的函数 $f(n)=3\ast n+3$
  • 二分查找算法的函数 $f(n)=(floor(lo{g}_2(n))+1)\ast 5+4$

• 为了对 $f(n)$ 进行化简，应当抓住主要矛盾，找到一个变化趋势与之相近的表示法

大 $O$ 表示法

其中

• $c,c_1,c_2$ 都为一个常数
• $f(n)$ 是实际执行代码行数与 n 的函数
• $g(n)$ 是经过化简，变化趋势与 $f(n)$ 一致的 n 的函数

渐进上界

渐进上界（asymptotic upper bound）：从某个常数 $n_0$开始，$c\ast g(n)$ 总是位于 $f(n)$ 上方，那么记作 $O(g(n))$

• 代表算法执行的最差情况

例1

• $f(n)=3\ast n+3$
• $g(n)=n$
• 取 $c=4$，在$n_0=3$ 之后，$g(n)$ 可以作为 $f(n)$ 的渐进上界，因此表示法写作 $O(n)$

例2

• $f(n)=5\ast floor(lo{g}_2(n))+9$
• $g(n)=lo{g}_2(n)$
• $O(lo{g}_2(n))$

已知 $f(n)$ 来说，求 $g(n)$

• 表达式中相乘的常量，可以省略，如
  • $f(n)=100\ast n^2$ 中的 $100$
• 多项式中数量规模更小（低次项）的表达式，如
  • $f(n)=n^2+n$ 中的 $n$
  • $f(n)=n^3+n^2$ 中的 $n^2$
• 不同底数的对数，渐进上界可以用一个对数函数 $\log n$ 表示
  • 例如：$lo{g}_2(n)$ 可以替换为 $lo{g}_{10}(n)$，因为 $lo{g}_2(n)=\frac{lo{g}_{10}(n)}{lo{g}_{10}(2)}$，相乘的常量 $\frac{1}{lo{g}_{10}(2)}$ 可以省略
• 类似的，对数的常数次幂可省略
  • 如：$log(n^c)=c\ast log(n)$

常见大 $O$ 表示法

按时间复杂度从低到高

• 黑色横线 $O(1)$，常量时间，意味着算法时间并不随数据规模而变化
• 绿色 $O(log(n))$，对数时间
• 蓝色 $O(n)$，线性时间，算法时间与数据规模成正比
• 橙色 $O(n\ast log(n))$，拟线性时间
• 红色 $O(n^2)$ 平方时间
• 黑色朝上 $O(2^n)$ 指数时间
• 没画出来的 $O(n!)$

空间复杂度

与时间复杂度类似，一般也使用大 $O$ 表示法来衡量：一个算法执行随数据规模增大，而增长的额外空间成本

二分查找性能

下面分析二分查找算法的性能

时间复杂度

• 最坏情况：$O(\log n)$
• 最好情况：如果待查找元素恰好在数组中央，只需要循环一次 $O(1)$

空间复杂度

• 需要常数个指针 $i,j,m$，因此额外占用的空间是 $O(1)$

5.平衡版

思想：

1. 左闭右开的区间，$i$ 指向的可能是目标，而 $j$ 指向的不是目标
2. 不奢望循环内通过 $m$ 找出目标, 缩小区间直至剩 1 个, 剩下的这个可能就是要找的（通过 $i$）
   • $j-i>1$ 的含义是，在范围内待比较的元素个数 > 1
3. 改变 $i$ 边界时，它指向的可能是目标，因此不能 $m+1$
4. 循环内的平均比较次数减少了
5. 时间复杂度 $\Theta (log(n))$

public static int binarySearch(int[] arr, int target) {int min = 0, max = arr.length;while (1 < max - min) {int mid = (min + max) >>> 1;if (target < arr[mid]) {max = mid;} else {min = mid;}}return (arr[min] == target) ? min : -1;
}

6.Leftmost 查询最左侧重复元素

public static int leftMost(int[] arr, int target) {int min = 0, max = arr.length - 1;int result = -1;//记录候选位置while (min <= max) {int mid = (min + max) >>> 1;int midVal = arr[mid];if (target < midVal) {max = mid - 1;} else if (midVal < target) {min = mid + 1;} else {result = mid;max = mid - 1;}}return result;
}

返回 >=target 的最靠左索引

• leftmost 返回值的另一层含义：$<target$ 的元素个数
• 小于等于中间值，都要向左找

public static int leftMost(int[] arr, int target) {int min = 0, max = arr.length - 1;while (min <= max) {int mid = (min + max) >>> 1;if (target <= arr[mid]) {max = mid - 1;} else {min = mid + 1;}}//返回 >=target 的最靠左索引return min;
}

7.Rightmost 查询最右侧重复元素

public static int rightMost(int[] arr, int target) {int min = 0, max = arr.length - 1;int result = -1;while (min <= max) {int mid = (min + max) >>> 1;int midVal = arr[mid];if (target < midVal) {max = mid - 1;} else if (midVal < target) {min = mid + 1;} else {result = mid;min = mid + 1;}}return result;
}

返回<=target 的最靠右索引

大于等于中间值，都要向右找

public static int rightMost(int[] arr, int target) {int min = 0, max = arr.length - 1;while (min <= max) {int mid = (min + max) >>> 1;if(target < arr[mid]){max = mid - 1;}else{min = mid + 1;}}//返回<=target 的最靠右索引return min - 1;
}

8.Leetcode 练习

• 704题
• 35题
• 34题