| 39、【查找】二分查找：数的范围和查找某个数（C/C++版） | 您所在的位置：网站首页 › bsearchc语言确定数组下标 › 39、【查找】二分查找：数的范围和查找某个数（C/C++版） |
39、【查找】二分查找：数的范围和查找某个数（C/C++版）
|
算法思想
二分查找（折半查找） 是针对有序序列的一种快速查找方式，与高中时候数学中学的二分法有异曲同工之处。通过不断缩小目标值所在区间的范围实现快速查找到目标值。每次将目标值与区间内的中位数进行比较，比中位数小则在中位数的做区间内再查找，如果比中位数大则在中位数的有区间内再查找，以相同的规则作用于缩小后的区间，以此类推最终便可找到结果。 对于整数二分 单调性（有序序列）仅为二分查找的充分条件，而不是必要条件，即具有单调性的序列一定可以进行二分查找，而可以进行二分查找的数列不一定具有单调性，非单调性的数列也有可能可以进行二分查找。
（1）向下取整 （2）向上取整 （1）向下取整 （2）向上取整 取表中下标较靠后的位置，同时也是两个数中较大的那个数。 算法实现注意事项 （1）当 while循环 判定条件为 l int mid = l + (r - l) / 2; // check()：为判断q[mid]是否满足某种规定或性质 //if(check(q[mid])) r = mid; // 假设此时的目标是寻找x，在左侧区间 if(q[mid] >= x) r = mid; // 在右侧区间或等于q[mid] == x else l = mid + 1; } return l; } // l = -1, r = n - 1 int bsearch_2(int q[], int l, int r){ while(l while (l int l = 0, r = n - 1; while(l // 往左侧压缩，更新右边界 r = mid - 1; }else if(nums[mid] > target){ r = mid - 1; }else if(nums[mid] int l = 0, r = n - 1; while(l // 往右侧压缩，更新左边界 l = mid + 1; }else if(nums[mid] > target){ r = mid - 1; }else if(nums[mid] double eps = 1e-8; // 精度，一般比题中要求的再多两位 // l可为取值范围的左边界，r可为取值范围的有边界 while(max((l - r), 1) > 1e-8){ double mid = (l + r) / 2; // 若目标x小于mid，则在左区间找；否则在有区间找 if(check(mid)) r = mid; else l = mid; } return l; } 时间复杂度O(log n) 空间复杂度O(1) 例题1：数的范围给定一个按照升序排列的长度为 n 的整数数组，以及 q个查询。 对于每个查询，返回一个元素 k的起始位置和终止位置（位置从 0开始计数）。 如果数组中不存在该元素，则返回 -1 -1。 输入格式 第一行包含整数 n和 q，表示数组长度和询问个数。 第二行包含 n个整数（均在 1∼10000范围内），表示完整数组。 接下来 q行，每行包含一个整数 k，表示一个询问元素。 输出格式 共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。 如果数组中不存在该元素，则返回 -1 -1。 数据范围 1≤n≤100000 1≤q≤10000 1≤k≤10000 输入样例 6 3 1 2 2 3 3 4 3 4 5 输出样例 3 4 5 5 -1 -1 算法实现 #include const int N = 1e5 + 10; int main(){ int n, m; scanf("%d%d", &n, &m); int q[N]; for(int i = 0; i int mid = i + j >> 1; if(k int mid = i + j + 1>> 1; if(k >= q[mid]) i = mid; else j = mid - 1; } printf("%d", j); } //puts(""); printf("\n"); } return 0; }参考文章： AcWing 789. 二分模板笔记 另一解法 #include using namespace std; const int N = 1e5 + 10; int n, q, k; int nums[N]; int left_bound(int target){ int l = 0, r = n - 1; while(l r = mid - 1; }else if(nums[mid] > target){ r = mid - 1; }else if(nums[mid] int l = 0, r = n - 1; while(l l = mid + 1; }else if(nums[mid] > target){ r = mid - 1; }else if(nums[mid] cin >> n >> q; int l, r; for(int i = 0; i > nums[i]; while(q--){ cin >> k; l = left_bound(k); if(l == -1) cout |
假设某个区间被划分成两个具有不同性质的子区间，整数二分的本质就是可以分别找到两个子区间的左右边界，从而将两个不同性质的子区间划分出来。
参考文章： 二分查找又叫折半查找，是一种简单又快速的查找算法
因为二分查找是以中点来进行左右分割，因此类比于二叉树，可以将中点作为树根，左右两侧作为左右子树，用二叉树的形式来进行表示。 
由于二分查找的表为顺序表，因此向下取整的意义就是取表中下标较靠前的位置，同时也是两个数中较小的那个数。
【本文地址】