顿搜
飞过闲红千叶，夕岸在哪
类目归类
查找——算法设计 · 篇四
08/13
一、二分查找的实现
GitHub地址：二分查找的实现.cpp
首先需要将元素排序，再进行二分查找，查找方式和快速排序夹逼方法一样，但要注意：
1、如果high = n-1（即闭区间）, 那么条件为 while(high >= low) ，最后 high = middle -1;
2、如果high = n （开区间），那么条件为 while(high > low) ，最后 high = middle;
3、标准的找中间点的方法：mid = low+((high-low)>>1);
## 二、查找元素的上下限 > GitHub地址：查找元素的上下限.cpp > 下限索引：第一个不大于该元素的下标索引 > 上限索引：第一个大于该元素的下标索引 + ①、在一个有序序列中，查找某一个元素在该序列中的下限索引 > 和二分查找类似，知识条件不是等号 + ②、查找某一个元素在一个有序序列中的范围，包含该元素的上下限 ，为闭区间 > 1、首先判断该元素是否存在 > 2、然后将其分为两个有序序列，分别查找上下限
## 三、寻找多个集合的交集 > GitHub地址：寻找多个集合的交集.cpp + ①、查找两个无序数组的交集 > 1、先排序 > 2、查找元素个数少的数组在另一个数组中是否出现 > 3、以元素个数少的数组中的元素为基准，在另一数组中进行二分查找
## 四、旋转数组中的查找 > GitHub地址：旋转数组中的查找.cpp + ①、在一个无重复元素的已经被旋转过的数组中查找某一个元素 > 1、根据两个子数组的性质来划分情况，前半部分一定是升序 > 2、判断元素在哪个部分，进行查找 + ②、在一个有重复元素的旋转数组中查找某一个元素 > 1、同样使用二分查找的思想 > 2、此时前半部分可能是升序，也可能是降序，需分情况讨论
