二分查找
二分查找(Binary Search)又称折半查找，是一种高效率的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
二分查找原理
满足表中元素有序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成两个子表，根据中间关键字和查找关键字的关系在子表中查找，重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
二分查找分析
优点： 比较次数少，查找速度快，平均性能好。
缺点： 要求待查表为有序表，且插入删除困难。
适用范围： 不经常变动而查找频繁的有序列表。
时间复杂度： O( log 2 N ）
代码实现
/ C++ int binarySearch(vector<int>& nums, int target) { int mid; // 中间位置 int left = 0; // 左边界 int right = nums.size() - 1; // 右边界 while (left <= right) { // 折半查找 mid = left + (right - left) / 2; // 计算中间位置 if (nums[mid] == target) { // 与中间位置元素比较 return mid; // 查找成功，返回位置信息 } else if (target < nums[mid]) { // 小于中间位置元素 right = mid - 1; // 改变右边界 } else { // 大于中间位置元素 left = mid + 1; // 改变左边界 } } return -1; // 查找失败返回-1 }
三分查找
三分查找原理
三分查找，类似于二分查找，区别在于利用两个中间位置记录，将表分为三个子表。
三分查找分析
时间复杂度： O( log 3 N ）
代码实现
// C++ int trisectionSearch(vector<int>& nums, int target) { int midl; // 靠左中间位置 int midr; // 靠右中间位置 int left = 0; // 左边界 int right = nums.size() - 1; // 右边界 while (left <= right) { // 三分查找 midl = left + (right - left) / 3; // 计算靠左中间位置 midr = right - (right - left) / 3; // 计算靠右中间位置 if (target < nums[midl]) { // 小于靠左中间位置 right = midl - 1; // 改变右边界 } else if (target > nums[midr]) { // 大于靠右中间位置 left = midr + 1; // 改变左边界 } else if (target != nums[midl] && target != nums[midr]) { // 不等于左右中间位置 left = midl + 1; // 改变左边界 right = midr - 1; // 改变右边界 } else { // 等于左或右中间位置 return nums[midl] == target ? midl : midr; // 查找成功，返回位置信息 } } return -1; // 查找失败返回-1 }
算法分析
由时间复杂度看，三分查找是不是优于二分查找呢？
二分查找每次查询范围减少一半，需要查询的次数是 log 2 N ）。三分查找每次查询两个数字与目标数字比较，可以把查询范围缩小成原先的 1 / 3。查询次数就只有 log 3 N )
N，一下子就优化了这么多，那如果是四分，五分，六分，七分，N分岂不是能无限优化。
答案并非如此，因为二分法和三分法的渐进复杂度是一样的。
log 2 3 是个常数,因此对数函数的底对于算法的复杂度分析是没有意义的。
因此，无论是二分法，三分法，四分法，N分法······复杂度都是一样的，分的越多，代码反而越复杂，得不偿失。
————————————————
版权声明：本文为CSDN博主「Acx7」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
