思路原理:
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
要求如下：
搜索一个数，如果存在，返回其索引（从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
相关资源：DirectX修复工具V4.0增强版