算法与数据结构

平衡树

单调队列

折半查找

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

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

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

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

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

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