二分查找 l<r和l<=r
时间: 2023-10-06 15:03:23 浏览: 226
二分查找是一种常见的查找算法,它通过将待查找的有序数组一分为二,逐步缩小查找范围,直到找到目标元素或确定目标元素不存在为止。
在二分查找的过程中,我们需要确定查找的范围。常见的方式是使用两个变量l和r来表示查找范围,其中l为左边界,r为右边界。两者的关系可以有两种情况:l<r和l<=r。
1. 当l<r时,表示查找范围内至少存在一个元素,即查找范围不为空。在这种情况下,我们可以继续进行二分查找,将查找范围缩小一半,直到找到目标元素或确定目标元素不存在为止。
2. 当l<=r时,表示查找范围内可能存在一个或零个元素,即查找范围为空或仅包含一个元素。在这种情况下,我们可以直接判断查找范围内是否存在目标元素。如果存在,那么直接返回该元素;如果不存在,那么返回找不到的提示。
总结来说,二分查找中的l<r表示查找范围不为空,而l<=r表示查找范围为空或仅包含一个元素。具体如何处理取决于实际的业务逻辑和算法实现。
相关问题
用c语言和二分查找解决这个问题描述:描述:Given an array, find the number of [i,j] (i and j are the indexes of the array (数组下标), not values) tuples in the array that satisfy array[i]+array[j]<=k. 输入:There are several test cases. For each test case, The first line contains two positive integers n (1<=n<=10^5) and k (1<=k<=10^18). The second line contains n integers, and the ith integer represents the value of array[i](1<= array[i]<=10^9). 输出:For each test case, output an integer representing the answer.
好的,让我解释一下这个问题的意思。题目要求我们在一个给定的数组中,找到所有满足条件 array[i]+array[j]<=k 的下标对 [i,j],并输出满足条件的下标对数量。
下面是使用 C 语言和二分查找算法的解法:
```c
#include<stdio.h>
#include<stdlib.h>
#define MAXN 100005
long long a[MAXN];
int cmp(const void *a, const void *b)
{
return *(long long *)a - *(long long *)b;
}
int binary_search(long long *a, int l, int r, long long x)
{
int mid;
while (l <= r) {
mid = l + (r - l) / 2;
if (a[mid] <= x) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return r;
}
int main()
{
int n;
long long k;
while (scanf("%d%lld", &n, &k) != EOF) {
for (int i = 0; i < n; i++) {
scanf("%lld", &a[i]);
}
qsort(a, n, sizeof(long long), cmp);
long long ans = 0;
for (int i = 0; i < n; i++) {
int j = binary_search(a, i+1, n-1, k-a[i]);
ans += j - i;
}
printf("%lld\n", ans);
}
return 0;
}
```
首先,我们需要对输入的数组进行排序,这样可以方便我们使用二分查找算法。然后,我们遍历数组中的每个元素 a[i],在剩下的 a[i+1] 至 a[n-1] 中寻找满足条件的元素 a[j],即 a[j] <= k - a[i]。我们可以使用二分查找算法在剩下的元素中查找满足条件的元素,从而求得满足条件的下标对数量。最后,我们将所有满足条件的数量累加起来,即为最终的答案。
注意,题目中给出的数组下标从 0 开始,而二分查找算法中的下标 i、j 都从 1 开始,因此在二分查找函数中,我们需要将 i+1 转换为实际的下标。
时间复杂度为 O(nlogn)。
while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid; else r = mid - 1; } return l;
这段代码是二分查找的实现,其中 `check()` 函数是用来检查当前二分的中间值是否满足条件的,`l` 和 `r` 分别表示当前二分的左右边界,最终返回的是满足条件的最大值。
具体来说,该算法首先将中间值计算为 `(l+r+1)/2`,然后调用 `check(mid)` 来检查中间值是否满足条件。如果满足条件,那么说明答案可能在右半区间,将左边界 `l` 更新为中间值,继续二分右半区间;否则说明答案可能在左半区间,将右边界 `r` 更新为中间值减一,继续二分左半区间。
最终返回的是满足条件的最大值,因为 `l` 和 `r` 最终会收敛到一个值,而这个值是满足条件的最大值。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)