当前位置：首页 > news >正文

网站开发介绍网站推广app下载

news 2025/8/2 4:56:24

网站开发介绍,网站推广app下载,快速做自适应网站,武汉光谷空轨1.概念二分查找算法也称折半查找，是一种非常高效的工作于有序数组的查找算法。需求：在有序数组 A A A 内，查找值 t a r g e t target target 如果找到返回索引如果找不到返回 − 1 -1 −1 前提给定一个内含 n n n 个元素的有序数组…

1.概念

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

需求：在有序数组 $A$ 内，查找值 $t a r g e t$

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

前提	给定一个内含 $n$ 个元素的有序数组 $A$ ，满足 $A_{0}\leq A_{1}\leq A_{2}\leq \cdots \leq A_{n-1}$ ，一个待查值 $t a r g e t$
1	设置 $i = 0$ ， $j = n - 1$
2	如果 $\gt j$ ，结束查找，没找到
3	设置 $floor(\frac {i+j}{2})$ ， $m$ 为中间索引， $f l oor$ 是向下取整（ $\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$ ，结束查找，找到了

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 * n + 3$
- 二分查找算法的函数 $f(n) = (floor(log_2(n)) + 1) * 5 + 4$
为了对 $f (n)$ 进行化简，应当抓住主要矛盾，找到一个变化趋势与之相近的表示法

大 $O$ 表示法

在这里插入图片描述

其中

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

渐进上界

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

代表算法执行的最差情况

例1

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

例2

$f(n) = 5*floor(log_2(n)) + 9$
$g(n) = log_2(n)$
$O(log_2(n))$

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

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

常见大 $O$ 表示法

在这里插入图片描述

按时间复杂度从低到高

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

空间复杂度

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

二分查找性能

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

时间复杂度

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

空间复杂度

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

5.平衡版

思想：

左闭右开的区间， $i$ 指向的可能是目标，而 $j$ 指向的不是目标
不奢望循环内通过 $m$ 找出目标, 缩小区间直至剩 1 个, 剩下的这个可能就是要找的（通过 $i$ ）
- $j - i > 1$ 的含义是，在范围内待比较的元素个数 > 1
改变 $i$ 边界时，它指向的可能是目标，因此不能 $m + 1$
循环内的平均比较次数减少了
时间复杂度 $\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 返回值的另一层含义： $\lt 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;
}