算法与数据结构

曼彻斯特编码和差分曼彻斯特编码

以下是关于曼彻斯特编码和差分曼彻斯特编码的介绍：

曼彻斯特编码

原理：在曼彻斯特编码中，每一位的中间有一跳变，位中间的跳变既作时钟信号，又作数据信号。从高到低跳变表示“0”，从低到高跳变表示“1”。
特点：具有自同步能力，将时钟和数据包含在数据流中，在传输代码信息的同时，也将时钟同步信号一起传输到对方；不存在直流分量，抗干扰性能良好；但每一个码元都被调成两个电平，数据传输速率只有调制速率的1/2，传输流的速率是原始数据流的两倍，要占用较宽的频带。
应用：常用于局域网传输，如以太网媒介系统。

差分曼彻斯特编码

原理：每位中间的跳变仅提供时钟定时，用每位开始时有无跳变表示“0”或“1”，有跳变为“0”，无跳变为“1”。
特点：相比曼彻斯特编码，变化更少，更适合传输高速信息；同样自带时钟信号，但同步时依赖于前一个比特的跳变，同步性稍弱；每位码元中心存在跳变，可用于同步。
应用：常用于高速数据传输场景，如光纤通信，也用于令牌环网。

两者区别

编码规则：曼彻斯特编码以位中间的跳变方向确定数据；差分曼彻斯特编码以位开始处有无跳变确定数据。
信号变化：曼彻斯特编码每位的电平变化相对固定；差分曼彻斯特编码的变化取决于前后位的关系，变化相对少。
同步性：曼彻斯特编码通过每个比特中间的跳变同步；差分曼彻斯特编码依赖前一个比特的跳变来同步，同步过程相对复杂。

平衡树

单调队列

折半查找

折半查找是一种在有序数组中查找指定元素的算法。其基本原理是将数组一分为二，然后判断要查找的元素位于哪一半，并继续在该半中进行查找，直到找到该元素或确定不存在。

在折半查找中，有几个细节需要注意：

数组必须是有序的：在执行折半查找之前，需要确保数组已按照升序或降序排列，否则无法保证查找的正确性。
中间索引的选择：确定中间索引的方法是将数组下界和上界相加后除以2，例如mid = (low + high) / 2。如果数组的长度为偶数，通常可以向下取整；如果需要向上取整，则可以使用mid = (low + high + 1) / 2。
判断条件的设置：在每次迭代中，需要根据当前中间元素与目标元素的大小关系来更新搜索范围。如果中间元素小于目标元素，则更新下界为mid+1；如果中间元素大于目标元素，则更新上界为mid-1；如果中间元素等于目标元素，则找到目标元素，返回其索引。

在某些特定应用中，可以通过修改判断细节来实现不同的折半查找方式：

查找第一个出现的目标元素：在执行更新搜索范围的操作时，如果中间元素等于目标元素，则将上界更新为mid-1，以继续在前半部分查找第一个出现的目标元素。
查找最后一个出现的目标元素：同样，在更新搜索范围时，如果中间元素等于目标元素，则将下界更新为mid+1，以继续在后半部分查找最后一个出现的目标元素。
查找第一个大于目标元素的元素：在更新搜索范围时，如果中间元素小于或等于目标元素，则将下界更新为mid+1，以继续在后半部分查找第一个大于目标元素的元素。
查找最后一个小于目标元素的元素：同样，在更新搜索范围时，如果中间元素大于或等于目标元素，则将上界更新为mid-1，以继续在前半部分查找最后一个小于目标元素的元素。

通过修改这些判断细节，可以使折半查找适应不同的特定应用，实现更加灵活和高效的查找功能。