二分查找

思路原理:

　　首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

要求如下：

　　搜索一个数，如果存在，返回其索引（从0开始），否则返回 -1。若出现多个数，返回第一个索引。

 1 int Mid_Search(vector<int> &arry, int target) {
 2 　　if (arry.size() == 0)
 3 　　　　return -1;
 4 　　int left = 0;
 5 　　int right = arry.size();      
 6 　　while (left < right) { 　　　　//为什么不是<=
 7 　　　　int mid = left + (right - left) / 2;　　　　//防止溢出
 8 　　　　if (arry[mid] == target)
 9 
10 　　　　　　right = mid;　　　　//　　　　为什么不直接返回索引
11 　　　　else if (arry[mid]>target)
12 
13 　　　　　　right = mid;　　　　//为什么这里不是mid - 1
14 　　　　else
15 
16 　　　　　　left = mid + 1;　　　　
17 　　}
18 　　if (left == arry.size())　　　　//为什么这样写？
19 
20 　　　　return -1;
21 　　return arry[left] == target ? left : -1;　　　　
22 }        

 1 int main() {
 2 　　srand((unsigned)time(NULL));　　　　    //产生随机数，#include<ctime>
 3 　　vector<int> arry;
 4 　　for (int i = 0; i < 10; i++) {
 5 　　　　arry.push_back(random(0,10));　　　　//宏定义，#define random(a,b) (rand()%(b-a)+a)
 6 　　}
 7 　　sort(arry.begin(), arry.end());　　　　//#include<algorithm>
 8 　　int index = Mid_Search(arry, 2);　　　　//查找数字2
 9 　　for (int i = 0; i < arry.size(); i++) {
10 　　　　cout << arry[i] << "\t";
11 　　}
12 　　cout << endl;
13 　　cout << index << endl;
14 　　return 0;
15 }

1.为什么不是<=　　因为right 初始化为 nums.size()，所以搜素区间为[left,right),写成<=区间变成了[left,right]

2.为什么不直接返回索引　　　　因为不能确定是不是mid那个值是第一个出现的值，如{1,2,2,2,3}

3.为什么有mid 和 mid - 1 的区分　　　　因为区间划分成[left,mid) 和 [mid + 1,right]

4.left == arry.size() 　　　　代表找不到查找的数字时返回-1

 

　　

原文链接:https://www.cnblogs.com/Jovesun/p/11185271.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有