二分查找算法

定义

二分查找又称折半查找，首先，假设表中元素是按升序排序，将表中间位置的关键字与查找关键字比较： 如果两者相等，则查找成功； 否则利用该中间位置，划分出前、后两个子表： ①如果中间位置的关键字大于查找关键字，则进一步查找前一个子表。 ②否则查找后一个子表。 重复上述的过程，直到找到目标关键字，输出查找成功，或者查到子表不存在为止，则查找不成功。

比如，待搜索数字target == 2 数组A = [-1,2,5,20,90,100,207,800]

待查找值target = 2 下标：[ 0, 1, 2, 3, 4, 5, 6, 7] nums：[-1,2,5,20,90,100,207,800]

第一次搜索： 搜索区域:[0,7][-1,2,5,20,90,100,207,800] 搜索target = 2 小于 nums[mid] = 20；

第二次搜索： 搜索区域:[0,2][-1,2,5] 搜索target = 2 等于 nums[mid] == 2； 故找到

递归形式如下：

bool binary_search(vector<int> &sort_array, int begin, int end, int target){ if(begin > end){ return false; } int mid = (begin + end) / 2; if(target == sort_array[mid]){ return true; } else if(target < sort_array[mid]){ return binary_search(sort_array, begin, mid - 1, target); } else if(target > sort_array[mid]){ return binary_search(sort_array, mid + 1, end, target); }

循环的形式如下：

bool binary_search(vector<int> &sort_array, int target){ int begin = 0; int end = sort_array.size() - 1; while(begin <= end){ int mid = (begin + end) / 2; if(target == sort_array[mid]){ return true; } else if(target < sort_array[mid]){ end = mid - 1; } else if(target > sort_array[mid]){ begin = mid + 1; } } return false; }

致谢

本章知识点和思路由小象学院相关视频提供，由本人学习并梳理得出，希望自己加深记忆的同时，也能给大家提供更多有关于一些算法的知识点。 你的点赞、评论、收藏就是对我最大的支持与鼓励，谢谢！