建设银行网站怎么登陆不,做网站首页的尺寸,口碑营销的好处,上海网站建设公司地版本说明
当前版本号[20230926]。
版本修改说明20230926初版
目录 文章目录 版本说明目录二分查找基础版算法描述分步演示情况一#xff1a;能在有序数组找到待查值情况二#xff1a;不能在有序数组找到待查值 翻译成代码基础版代码#xff08;包括测试类#xff09;疑惑…版本说明
当前版本号[20230926]。
版本修改说明20230926初版
目录 文章目录 版本说明目录二分查找基础版算法描述分步演示情况一能在有序数组找到待查值情况二不能在有序数组找到待查值 翻译成代码基础版代码包括测试类疑惑解答基础版改良后代码 进阶版改动地方改动一i 跟 j 的边界位置改动二while 的条件改动三if 判断中的 j 的边界问题 改动后代码分步演示改动地方的解释i 跟 j 的边界位置改动原因while 的条件改动原因if 判断中的 j 的边界问题改动原因 衡量算法好坏时间复杂度如何表示时间复杂度大 O O O 表示法渐进上界常见大 O O O 表示法渐进下界渐进紧界 空间复杂度二分查找性能 平衡版算法题实战力扣704 . 二分查找 二分查找
二分查找算法也称折半查找是一种非常高效的工作于有序数组的查找算法。后续的课程中还会学习更多的查找算法但在此之前不妨用它作为入门。
基础版
需求在有序数组 A A A 内查找值 t a r g e t target target
如果找到返回索引如果找不到返回 − 1 -1 −1
算法描述
前提给定一个内含 n n n 个元素的有序数组 A A A满足 A 0 ≤ A 1 ≤ A 2 ≤ ⋯ ≤ A n − 1 A_{0}\leq A_{1}\leq A_{2}\leq \cdots \leq A_{n-1} A0≤A1≤A2≤⋯≤An−1一个待查值 t a r g e t target target1设置 i 0 i0 i0 j n − 1 jn-1 jn−12如果 i j i \gt j ij结束查找没找到3设置 m f l o o r ( i j 2 ) m floor(\frac {ij}{2}) mfloor(2ij) m m m 为中间索引 f l o o r floor floor 是向下取整 ≤ i j 2 \leq \frac {ij}{2} ≤2ij 的最小整数4如果 t a r g e t A m target A_{m} targetAm 设置 j m − 1 j m - 1 jm−1跳到第2步5如果 A m t a r g e t A_{m} target Amtarget 设置 i m 1 i m 1 im1跳到第2步6如果 A m t a r g e t A_{m} target Amtarget结束查找找到了
分步演示
情况一能在有序数组找到待查值
1、给定一个有序数组并且在其下面标上下标。 2、设置一个i值和一个j值i从数组第0号元素左边开始检索j从数组最后一个元素右边开始检索。 3、设定一个可以在数组中能找到的数值36 作为待查值target。接着开始二分查找。首先找第一次的中间索引 m 使用公式 m f l o o r ( i j 2 ) m floor(\frac {ij}{2}) mfloor(2ij) 可知m07/ 2 3.5 向下求值后可得m3。 4、**判断第一次中间索引与待查值的大小。**发现 m 所对应的数为 28小于待查值 36.就将 i 设置成 m1 . 5、接着找第二次的中间索引 m 使用公式 m f l o o r ( i j 2 ) m floor(\frac {ij}{2}) mfloor(2ij) 可知m47/ 2 5.5 向下求值后可得m5。 6、**判断第二次中间索引与待查值的大小。**发现 m 所对应的数为 38大于待查值 36.就将 j 设置成 m-1 . 7、接着找第三次的中间索引 m 使用公式 m f l o o r ( i j 2 ) m floor(\frac {ij}{2}) mfloor(2ij) 可知m44/ 2 4 . 8、**判断第三次中间索引与待查值的大小。**发现 m 所对应的数为 36等于待查值 36.到这里我们就通过二分查找找到了待查值。
情况二不能在有序数组找到待查值
1、给定一个有序数组并且在其下面标上下标。【与上同】 2、设置一个i值和一个j值i从左边开始检索j从右边开始检索。【与上同】 3、设定一个可以在数组中能呗找到的数值26 作为待查值target。接着开始二分查找。首先找第一次的中间索引 m 使用公式 m f l o o r ( i j 2 ) m floor(\frac {ij}{2}) mfloor(2ij) 可知m07/ 2 3.5 向下求值后可得m3。【与上同】 4、**判断第一次中间索引与待查值的大小。**发现 m 所对应的数为 28大于待查值 26.就将 j 设置成 m-1 . 5、接着找第二次的中间索引 m 使用公式 m f l o o r ( i j 2 ) m floor(\frac {ij}{2}) mfloor(2ij) 可知m02/ 2 1 . 6、**判断第二次中间索引与待查值的大小。**发现 m 所对应的数为 12小于待查值 36.就将 i 设置成 m1 . 7、接着找第三次的中间索引 m 使用公式 m f l o o r ( i j 2 ) m floor(\frac {ij}{2}) mfloor(2ij) 可知m22/ 2 2 . 8、**判断第三次中间索引与待查值的大小。**发现 m 所对应的数为 20小于待查值 36.我们再次将 i 设置成 m1 . 9、到这里我们能发现 i 已经大于 j 能够证明我们找不到了到此结束查找. P.S. 对于一个算法来讲都有较为严谨的描述上面是一个例子后续讲解时以简明直白为目标不会总以上面的方式来描述算法 翻译成代码
以情况一能在有序数组找到待查值 进行演示
1、给定一个有序数组。 【这一步可以通过测试代码进行测试、输出放到后面去详细解释】 2、设置一个i值和一个j值i从左边开始检索j从右边开始检索。 这句话可以翻译成以下代码
int i 0;
int j a.length - 1;3、设定一个可以在数组中能找到的待查值target。接着开始二分查找。首先找中间索引 m 使用公式 m f l o o r ( i j 2 ) m floor(\frac {ij}{2}) mfloor(2ij) 。在java中 int m (ij) / 2 ; 会自动地向下取整。 这句话可以翻译成以下代码
while(i j) //只有在i j中才可以通过二分查找找到数值{int m (ij) / 2 ;}
return -1 //当i j中就证明无法找到了4、**判断中间索引与待查值的大小。**发现 m 小于待查值就将 **i 设置成 m1 .**若发现 m 大于待查值 36.就将 j 设置成 m-1 .如果发现 m 等于待查值就证明找到了直接返回m值即可。 这句话可以翻译成以下代码
if(a[m] target) //目标待查值在m的左边{j m - 1;}else if (a[m] target)//目标待查值在m的右边{i m 1;}else //目标待查值等于m证明找到了{return m;}基础版代码包括测试类
本代码仍然可以正常运行不过如果想有更好更优化的代码可以向下继续观看。
public class 二分查找 {public static int binarySearch(int[] a, int target) {int i 0;int j a.length - 1;while(i j) //只有在i j中才可以通过二分查找找到数值{int m (ij) / 2 ; //这里有点小问题但不影响代码运行具体可以跳到《疑惑解答》去了解if(a[m] target) //目标待查值在m的左边{j m - 1;}else if (a[m] target)//目标待查值在m的右边{i m 1;}else //目标待查值等于m证明找到了{return m;}}return -1; //当i j中就证明无法找到了}
}同时你也可以自己写一个junit测试类来测试这段代码是否能正常运行
package SuanFa.test;import org.junit.jupiter.api.DisplayName;import SuanFa.第一章_初始算法.数组.二分查找;import static org.junit.jupiter.api.Assertions.*;class 二分查找Test {org.junit.jupiter.api.TestDisplayName(binarySearch 找到)void testbinarySearch() {int[] a {7, 13, 24, 45, 66, 82, 94};assertEquals(0,二分查找.binarySearch(a, 7));}
}然后发现测试是正常可运行的证明我们代码暂时没有出现问题。 疑惑解答
问那为什么是ij 意味着区间内有未比较的元素而不是 ij 答因为 i , j 它们指向的元素也会参与比较
问使用 (ij) / 2 会不会出现问题呢
答第一段代码中计算m的方式是(ij) / 2这是整数除法会直接舍去小数部分。这种方式在m恰好是两个整数的中间值时可能会导致问题因为如果i和j都是奇数那么m就会偏向于左边导致可能无法找到目标值。
所以我们可以进行一个改良把计算m的方式改成(i j) 1这是无符号右移操作可以保证无论i和j的值如何m都会取到它们中间位置的整数。这种方式可以避免上述问题。
基础版改良后代码
public static int binarySearch(int[] a, int target) {int i 0, j a.length - 1;while (i j) {int m (i j) 1; // 可以避免m找不到中间值的问题if (target a[m]) { // 在左边j m - 1;} else if (a[m] target) { // 在右边i m 1;} else {return m;}}return -1;
}进阶版
进阶版相对于基础版会进行三个地方的改动
改动地方
改动一i 跟 j 的边界位置
不希望j指的区域参与比较运算
int i 0;
int j a.length;改动二while 的条件 while(i j) {……}改动三if 判断中的 j 的边界问题
if(a[m] target) {j m;}改动后代码
package SuanFa.第一章_初始算法.数组;public class 二分查找 {public static int binarySearch(int[] a, int target) {int i 0;int j a.length;while(i j) {int m (ij) 1 ;if(a[m] target){j m;}else if (a[m] target){i m 1;}else {return m;}}return -1;}
}分步演示
1、给定一个有序数组并且在其下面标上下标。并设置一个i值和一个j值i从数组第0个元素开始向左检索j从外界区域开始向右检索。 2、设定一个可以在数组中能找到的数值26 作为待查值target。接着开始二分查找。首先找第一次的中间索引 m 使用公式 m f l o o r ( i j 2 ) m floor(\frac {ij}{2}) mfloor(2ij) 可知m08 1 4 3、**判断第一次中间索引与待查值的大小。**发现 m 所对应的数为 33大于待查值 26.就将 j 设置成 m . 4、接着找第二次的中间索引 m 使用公式 m f l o o r ( i j 2 ) m floor(\frac {ij}{2}) mfloor(2ij) 可知m04 1 2. 5、**判断第二次中间索引与待查值的大小。**发现 m 所对应的数为 20小于待查值 26.就将 i 设置成 m1 . 6、接着找第三次的中间索引 m 使用公式 m f l o o r ( i j 2 ) m floor(\frac {ij}{2}) mfloor(2ij) 可知m34 1 3 .向下求值 7、**判断第三次中间索引与待查值的大小。**发现 m 所对应的数为 26等于待查值 26.到这里我们就通过二分查找找到了待查值。
改动地方的解释
i 跟 j 的边界位置改动原因
改动原因不希望 j 指的区域参与比较运算j 只需要作为 a.length 下标为8 的元素即可 while 的条件改动原因
改动原因i 的区域是要参与比较运算的而 j 不需要。如果出现等于号就有可能出现 i 带着 j 一起进行运算了。
注当仅修改了 j a.length 的条件却没有改动 while 中 i j 在查找数组中不存在的元素的话就会发生死循环
示例
1、给定一个有序数组并且在其下面标上下标。并设置一个i值和一个j值i从数组第0个元素开始向左检索j从外界区域开始向右检索。 2、设定一个可以在数组中找不到的数值27 作为待查值target。接着开始二分查找。首先找第一次的中间索引 m 使用公式 m f l o o r ( i j 2 ) m floor(\frac {ij}{2}) mfloor(2ij) 可知m08 1 4 3、**判断第一次中间索引与待查值的大小。**发现 m 所对应的数为 33大于待查值 27.就将 j 设置成 m . 4、接着找第二次的中间索引 m 使用公式 m f l o o r ( i j 2 ) m floor(\frac {ij}{2}) mfloor(2ij) 可知m04 1 2. 5、**判断第二次中间索引与待查值的大小。**发现 m 所对应的数为 20小于待查值 27.就将 i 设置成 m1 . 6、接着找第三次的中间索引 m 使用公式 m f l o o r ( i j 2 ) m floor(\frac {ij}{2}) mfloor(2ij) 可知m34 1 3 .向下求值 7、**判断第三次中间索引与待查值的大小。**发现 m 所对应的数为 26小于待查值 27.再将 i 设置成 m1 . 8、接着找第四次的中间索引 m 使用公式 m f l o o r ( i j 2 ) m floor(\frac {ij}{2}) mfloor(2ij) 可知m44 1 4 . 9、**判断第四次中间索引与待查值的大小。**发现 m 所对应的数为 33大于待查值 27.再将 **j 设置成 m .**但由于原本的 j 就在下标为4的位置此时就开始陷入死循环里了。
if 判断中的 j 的边界问题改动原因
改动三就很简单了这里就不多赘述了。
衡量算法好坏
时间复杂度
下面的查找算法也能得出与之前二分查找一样的结果那你能说出它差在哪里吗
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 n 的影响比较 n 1 n1 n1 次i 受数组元素个数 n n n 的影响自增 n n n 次a[i] k 受元素个数 n n n 的影响比较 n n n 次return -1执行一次
粗略认为每行代码执行时间是 t t t假设 n 4 n4 n4 那么
总执行时间是 ( 1 4 1 4 4 1 ) ∗ t 15 t (141441)*t 15t (141441)∗t15t可以推导出更一般地公式为 T ( 3 ∗ n 3 ) t T (3*n3)t T(3∗n3)t
如果套用二分查找算法还是 [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 比较 f l o o r ( log 2 ( n ) 1 ) floor(\log_{2}(n)1) floor(log2(n)1) 再加 1 次 (i j) 1 计算 f l o o r ( log 2 ( n ) 1 ) floor(\log_{2}(n)1) floor(log2(n)1) 次 接下来 if() else if() else 会执行 3 ∗ f l o o r ( log 2 ( n ) 1 ) 3* floor(\log_{2}(n)1) 3∗floor(log2(n)1) 次分别为 if 比较else if 比较else if 比较成立后的赋值语句 return -1执行一次
结果
总执行时间为 ( 2 ( 1 3 ) 3 3 ∗ 3 1 ) ∗ t 19 t (2 (13) 3 3 * 3 1)*t 19t (2(13)33∗31)∗t19t更一般地公式为 ( 4 5 ∗ f l o o r ( log 2 ( n ) 1 ) ) ∗ t (4 5 * floor(\log_{2}(n)1))*t (45∗floor(log2(n)1))∗t 注意 左侧未找到和右侧未找到结果不一样这里不做分析 两个算法比较可以看到 n n n 在较小的时候二者花费的次数差不多 但随着 n n n 越来越大比如说 n 1000 n1000 n1000 时用二分查找算法红色也就是 54 t 54t 54t而蓝色算法则需要 3003 t 3003t 3003t 计算机科学中时间复杂度是用来衡量一个算法的执行随数据规模增大而增长的时间成本
不依赖于环境因素
如何表示时间复杂度 假设算法要处理的数据规模是 n n n代码总的执行行数用函数 f ( n ) f(n) f(n) 来表示例如 线性查找算法的函数 f ( n ) 3 ∗ n 3 f(n) 3*n 3 f(n)3∗n3二分查找算法的函数 f ( n ) ( f l o o r ( l o g 2 ( n ) ) 1 ) ∗ 5 4 f(n) (floor(log_2(n)) 1) * 5 4 f(n)(floor(log2(n))1)∗54 为了对 f ( n ) f(n) f(n) 进行化简应当抓住主要矛盾找到一个变化趋势与之相近的表示法
大 O O O 表示法 其中 c , c 1 , c 2 c, c_1, c_2 c,c1,c2 都为一个常数 f ( n ) f(n) f(n) 是实际执行代码行数与 n 的函数 g ( n ) g(n) g(n) 是经过化简变化趋势与 f ( n ) f(n) f(n) 一致的 n 的函数
渐进上界
渐进上界asymptotic upper bound从某个常数 n 0 n_0 n0开始 c ∗ g ( n ) c*g(n) c∗g(n) 总是位于 f ( n ) f(n) f(n) 上方那么记作 O ( g ( n ) ) O(g(n)) O(g(n))
代表算法执行的最差情况
例1 f ( n ) 3 ∗ n 3 f(n) 3*n3 f(n)3∗n3 g ( n ) n g(n) n g(n)n取 c 4 c4 c4在 n 0 3 n_03 n03 之后 g ( n ) g(n) g(n) 可以作为 f ( n ) f(n) f(n) 的渐进上界因此表示法写作 O ( n ) O(n) O(n)
例2 f ( n ) 5 ∗ f l o o r ( l o g 2 ( n ) ) 9 f(n) 5*floor(log_2(n)) 9 f(n)5∗floor(log2(n))9 g ( n ) l o g 2 ( n ) g(n) log_2(n) g(n)log2(n) O ( l o g 2 ( n ) ) O(log_2(n)) O(log2(n))
已知 f ( n ) f(n) f(n) 来说求 g ( n ) g(n) g(n)
表达式中相乘的常量可以省略如 f ( n ) 100 ∗ n 2 f(n) 100*n^2 f(n)100∗n2 中的 100 100 100 多项式中数量规模更小低次项的表达式如 f ( n ) n 2 n f(n)n^2n f(n)n2n 中的 n n n f ( n ) n 3 n 2 f(n) n^3 n^2 f(n)n3n2 中的 n 2 n^2 n2 不同底数的对数渐进上界可以用一个对数函数 log n \log n logn 表示 例如 l o g 2 ( n ) log_2(n) log2(n) 可以替换为 l o g 10 ( n ) log_{10}(n) log10(n)因为 l o g 2 ( n ) l o g 10 ( n ) l o g 10 ( 2 ) log_2(n) \frac{log_{10}(n)}{log_{10}(2)} log2(n)log10(2)log10(n)相乘的常量 1 l o g 10 ( 2 ) \frac{1}{log_{10}(2)} log10(2)1 可以省略 类似的对数的常数次幂可省略 如 l o g ( n c ) c ∗ l o g ( n ) log(n^c) c * log(n) log(nc)c∗log(n)
常见大 O O O 表示法 按时间复杂度从低到高
黑色横线 O ( 1 ) O(1) O(1)常量时间意味着算法时间并不随数据规模而变化绿色 O ( l o g ( n ) ) O(log(n)) O(log(n))对数时间蓝色 O ( n ) O(n) O(n)线性时间算法时间与数据规模成正比橙色 O ( n ∗ l o g ( n ) ) O(n*log(n)) O(n∗log(n))拟线性时间红色 O ( n 2 ) O(n^2) O(n2) 平方时间黑色朝上 O ( 2 n ) O(2^n) O(2n) 指数时间没画出来的 O ( n ! ) O(n!) O(n!) ☞ 指n的阶乘是时间复杂度最大的
渐进下界
渐进下界asymptotic lower bound从某个常数 n 0 n_0 n0开始 c ∗ g ( n ) c*g(n) c∗g(n) 总是位于 f ( n ) f(n) f(n) 下方那么记作 Ω ( g ( n ) ) \Omega(g(n)) Ω(g(n))
渐进紧界
渐进紧界asymptotic tight bounds从某个常数 n 0 n_0 n0开始 f ( n ) f(n) f(n) 总是在 c 1 ∗ g ( n ) c_1*g(n) c1∗g(n) 和 c 2 ∗ g ( n ) c_2*g(n) c2∗g(n) 之间那么记作 Θ ( g ( n ) ) \Theta(g(n)) Θ(g(n))
空间复杂度
与时间复杂度类似一般也使用大 O O 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;
}二分查找性能
下面分析二分查找算法的性能
时间复杂度
最坏情况 O ( log n ) O(\log n) O(logn)最好情况如果待查找元素恰好在数组中央只需要循环一次 O ( 1 ) O(1) O(1)
空间复杂度
需要常数个指针 i , j , m i,j,m i,j,m因此额外占用的空间是 O ( 1 ) O(1) O(1)
平衡版
与前面的基础版与进阶版不同的是只用 if-else 即可
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 i i 指向的可能是目标而 j j j 指向的不是目标不奢望循环内通过 m m m 找出目标, 缩小区间直至剩 1 个, 剩下的这个可能就是要找的通过 i i i j − i 1 j - i 1 j−i1 的含义是在范围内待比较的元素个数 1 改变 i i i 边界时它指向的可能是目标因此不能 m 1 m1 m1循环内的平均比较次数减少了时间复杂度 Θ ( l o g ( n ) ) \Theta(log(n)) Θ(log(n))
算法题实战力扣704 . 二分查找
具体的解题过程可以跳转到我的另一篇博客进行观看代码随想录—力扣算法题704二分查找.Java版示例代码与导图详解
