12.5_黑马数据结构与算法Java

目录

001 二分查找 算法描述

002 二分查找 算法实现

003 二分查找 问题1 循环条件

004 二分查找 问题2 中间索引

thinking：反码补码原码？

thinking：二进制转十进制？

thinking：无符号右移？

005 二分查找 问题3 比较符号

006二分查找 改动版

007 如何衡量算法好坏01

008 如何衡量算法好坏02

​编辑​编辑

009 时间复杂度 大O表示法1

010 时间复杂度 大O表示法2

012 二分查找 平衡版

013 二分查找 JAVA版

thinking:System.arraycopy？

014 二分查找 LeftRightmost

015 二分查找 LeftRightmost 返回值

视频

基础数据结构-001-二分查找-算法描述_哔哩哔哩_bilibili

001 二分查找 算法描述

002 二分查找 算法实现

003 二分查找 问题1 循环条件

因为这次查询的最后时候，是i=j，且最后要查询的值也是当i=j的时候才拥有。

每一次的比较都有，但是单单缺少了最后一次的比较。也就是当i=j这一次。由于while循环的条件是i<j，因此因为i=j，就跳出while循环条件，从而输出-1 这个bug。

004 二分查找 问题2 中间索引

thinking：反码补码原码？

这里涉及到JAVA原码补码反码中的知识点，又恰巧当时学习黑马JAVA上的时候这节课跳过了。遂来补课。

运算符-12-多学一招原码反码补码_哔哩哔哩_bilibili

 8个bit=1个字节

thinking：二进制转十进制？

关于二进制与十进制互转的方法(简单好学！)_二进制转十进制_猿西西的博客-CSDN博客

 

 

因此，一个字节他的取值范围是正的127到负的128. 

右移一次，相当于除2

thinking：无符号右移？

在java中，总是将最高位视为符号位

接下来，我们来看回数据结构的视频。

产生这样的情况是因为，j本来是一个很大的数字，当第二次再加上j的时候，这个m就变得很大了，大到没有办法用计算机语言正常表示了，因为java中采用的有符号的表示方式。

有两种表现形式，一种是有符号的，一种是无符号的。无符号的表现形式就是正常的，但是java中采用的是有符号的，因此就会出现负数的情况。

因此采用无符号右移，解决这样的情况。而且也遵循除以2的原则，如果有小数的话，采用向下取整。

005 二分查找 问题3 比较符号

006二分查找 改动版

注重理解！

j指向的只是边界，而i指向的有可能还要参与比较。因此不可以加等于号，加了之后，j也就是边界也会参与比较。当查询的元素不存在的时候，就会出现死循环。因此，改动版的也称为左闭右开。而基础版的叫做左闭右闭。开：只是边界。闭：既是边界，又是有可能参与比较的东西。

007 如何衡量算法好坏01

008 如何衡量算法好坏02

一般采用事前分析法。

假设每一行代码的运行速率是相同的。

找出运行规律，计算两种代码运行了多少次。

当基数小的时候是看不出什么的，要让基数变大，才可以看出哪个算法好哪个算法不好。

二分查找法：找规律

左（二分查找），右（线性查找）

009 时间复杂度 大O表示法1

010 时间复杂度 大O表示法2

012 二分查找 平衡版

问题：当要查询的元素在最左边或者在最右边的时候，要查询的次数不相同

改动后：

013 二分查找 JAVA版

thinking:System.arraycopy？

System.arraycopy的使用方法详解_HiSiri666666的博客-CSDN博客

014 二分查找 LeftRightmost

left

Right

015 二分查找 LeftRightmost 返回值