二分查找又称折半查找,首先,假设表中元素是按升序排序,将表中间位置的关键字与查找关键字比较: 如果两者相等,则查找成功; 否则利用该中间位置,划分出前、后两个子表: ①如果中间位置的关键字大于查找关键字,则进一步查找前一个子表。 ②否则查找后一个子表。 重复上述的过程,直到找到目标关键字,输出查找成功,或者查到子表不存在为止,则查找不成功。
比如,待搜索数字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; }本章知识点和思路由小象学院相关视频提供,由本人学习并梳理得出,希望自己加深记忆的同时,也能给大家提供更多有关于一些算法的知识点。 你的点赞、评论、收藏就是对我最大的支持与鼓励,谢谢!