ETJava Beta | Java
注册
登录
注册
登录
注册
登录
定义
在数学和计算机科学领域，算法是一系列有限的严谨指令，通常用于解决一类特定问题或执行计算
In mathematics and computer science, an algorithm (/ˈælɡərɪðəm/) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation.[^1]
Introduction to Algorithm[^2]
不正式的说，算法就是任何定义优良的计算过程：接收一些值作为输入，在有限的时间内，产生一些值作为输出。
Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output in a finite amount of time.
定义
在计算机科学领域，数据结构是一种数据组织、管理和存储格式，通常被选择用来高效访问数据
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data
Introduction to Algorithm[^2]
数据结构是一种存储和组织数据的方式，旨在便于访问和修改
A data structure is a way to store and organize data in order to facilitate access and modifications
可以说，程序 = 数据结构 + 算法，它们是每一位程序员的基本功，下来我们通过对一个非常著名的二分查找算法的讲解来认识一下算法
二分查找算法也称折半查找，是一种非常高效的工作于有序数组的查找算法。后续的课程中还会学习更多的查找算法，但在此之前，不妨用它作为入门。
需求：在有序数组 \(A\) 内，查找值 \(target\)
算法描述
| 前提 | 给定一个内含 \(n\) 个元素的有序数组 \(A\)，满足 \(A_{0}\leq A_{1}\leq A_{2}\leq \cdots \leq A_{n-1}\)，一个待查值 \(target\) |
| 1 | 设置 \(i=0\)，\(j=n-1\) |
| 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\)，结束查找，找到了 |
P.S.
- 对于一个算法来讲，都有较为严谨的描述，上面是一个例子
- 后续讲解时，以简明直白为目标，不会总以上面的方式来描述算法
java 实现
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;
}
另一种写法
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;
}
时间复杂度
下面的查找算法也能得出与之前二分查找一样的结果，那你能说出它差在哪里吗？
public static int search(int[] a, int k) {
for (
int i = 0;
i < a.length;
i++
) {
if (a[i] == k) {
return i;
}
}
return -1;
}
考虑最坏情况下（没找到）例如 [1,2,3,4] 查找 5
int i = 0 只执行一次i < a.length 受数组元素个数 \(n\) 的影响，比较 \(n+1\) 次i++ 受数组元素个数 \(n\) 的影响，自增 \(n\) 次a[i] == k 受元素个数 \(n\) 的影响，比较 \(n\) 次return -1，执行一次粗略认为每行代码执行时间是 \(t\)，假设 \(n=4\) 那么
如果套用二分查找算法，还是 [1,2,3,4] 查找 5
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;
}
int i = 0, j = a.length - 1 各执行 1 次
i <= j 比较 \(floor(\log_{2}(n)+1)\) 再加 1 次
(i + j) >>> 1 计算 \(floor(\log_{2}(n)+1)\) 次
接下来 if() else if() else 会执行 \(3* floor(\log_{2}(n)+1)\) 次，分别为
return -1，执行一次
结果：
注意：
左侧未找到和右侧未找到结果不一样，这里不做分析
两个算法比较，可以看到 \(n\) 在较小的时候，二者花费的次数差不多
但随着 \(n\) 越来越大，比如说 \(n=1000\) 时，用二分查找算法（红色）也就是 \(54t\)，而蓝色算法则需要 \(3003t\)
画图采用的是 Desmos | 图形计算器
计算机科学中，时间复杂度是用来衡量：一个算法的执行，随数据规模增大，而增长的时间成本
如何表示时间复杂度呢？
假设算法要处理的数据规模是 \(n\)，代码总的执行行数用函数 \(f(n)\) 来表示，例如：
为了对 \(f(n)\) 进行化简，应当抓住主要矛盾，找到一个变化趋势与之相近的表示法
大 \(O\) 表示法[^4]
其中
渐进上界
渐进上界（asymptotic upper bound）：从某个常数 \(n_0\)开始，\(c*g(n)\) 总是位于 \(f(n)\) 上方，那么记作 \(O(g(n))\)
例1
例2
已知 \(f(n)\) 来说，求 \(g(n)\)
常见大 \(O\) 表示法
按时间复杂度从低到高
渐进下界
渐进下界（asymptotic lower bound）：从某个常数 \(n_0\)开始，\(c*g(n)\) 总是位于 \(f(n)\) 下方，那么记作 \(\Omega(g(n))\)
渐进紧界
渐进紧界（asymptotic tight bounds）：从某个常数 \(n_0\)开始，\(f(n)\) 总是在 \(c_1*g(n)\) 和 \(c_2*g(n)\) 之间，那么记作 \(\Theta(g(n))\)
空间复杂度
与时间复杂度类似，一般也使用大 \(O\) 表示法来衡量：一个算法执行随数据规模增大，而增长的额外空间成本
public static int binarySearchBasic(int[] a, int target) {
int i = 0, j = a.length - 1; // 设置指针和初值
while (i <= j) { // 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 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;
}
思想：
private static int binarySearch0(long[] a, int fromIndex, int toIndex,
long key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
long midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
有时我们希望返回的是最左侧的重复元素，如果用 Basic 二分查找
对于数组 \([1, 2, 3, 4, 4, 5, 6, 7]\)，查找元素4，结果是索引3
对于数组 \([1, 2, 4, 4, 4, 5, 6, 7]\)，查找元素4，结果也是索引3，并不是最左侧的元素
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;
}
应用
对于 Leftmost 与 Rightmost，可以返回一个比 -1 更有用的值
Leftmost 改为
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;
}
Rightmost 改为
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;
}
几个名词
范围查询：
求排名：\(leftmost(target) + 1\)
求前任（predecessor）：\(leftmost(target) - 1\)
求后任（successor）：\(rightmost(target)+1\)
求最近邻居：
用函数 \(f(n)\) 表示算法效率与数据规模的关系，假设每次解决问题需要 1 微秒（\(10^{-6}\) 秒），进行估算：
参考解答
一台机器对200个单词进行排序花了200秒(使用冒泡排序)，那么花费800秒，大概可以对多少个单词进行排序
a. 400
b. 600
c. 800
d. 1600
答案
解释
要点：减而治之，可以用递归或非递归实现
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1
例如
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
参考答案：略，可以用讲过的任意一种二分求解
要点：理解谁代表插入位置
给定一个排序数组和一个目标值
例如
输入: nums = [1,3,5,6], target = 5
输出: 2
输入: nums = [1,3,5,6], target = 2
输出: 1
输入: nums = [1,3,5,6], target = 7
输出: 4
参考答案1：用二分查找基础版代码改写，基础版中，找到返回 m，没找到 i 代表插入点，因此有
public int searchInsert(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 i; // 原始 return -1
}
参考答案2：用二分查找平衡版改写，平衡版中
public static int searchInsert(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 : i + 1;
// 原始 (target == a[i]) ? i : -1;
}
参考答案3：用 leftmost 版本解，返回值即为插入位置（并能处理元素重复的情况）
public int searchInsert(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;
}
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题
例如
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
输入：nums = [], target = 0
输出：[-1,-1]
参考答案
public static int left(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 right(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[] searchRange(int[] nums, int target) {
int x = left(nums, target);
if(x == -1) {
return new int[] {-1, -1};
} else {
return new int[] {x, right(nums, target)};
}
}
本文，已收录于，我的技术网站 pottercoding.cn，有大厂完整面经，工作技术，架构师成长之路，等经验分享!
官方公众号