作业介绍
C4.04 二分查找
课堂内容:二分查找
-
二分查找算法原理
二分查找也称折半查找,是一种在有序数组中查找某一特定元素的搜索算法。
-
二分查找_参考代码
int check(int nums[], int L, int R, int x)
{
int mid;
while (L <= R) // 当左边界小于等于右边界时,继续查找
{
mid = (L + R) / 2; // 计算中间索引
if (nums[mid] == x) // 如果中间元素等于 x,则返回其索引
return mid;
else if (nums[mid] < x) // 如果中间元素小于 x,则在右半部分继续查找
L = mid + 1;
else
R = mid - 1; // 如果中间元素大于 x,则在左半部分继续查找
}
return -1; // 如果循环结束仍未找到,则返回 -1
}
-
x最靠左的位置_左边界
因为找的是数的左边界,所以需要在 mid 的值的左区间继续寻找 5 ,当 x == nums[mid] 时,用 ans = 将可能答案记录,在让 R = mid - 1即可,这样我们就可以继续在 mid 的左区间继续找 5 ,直到搜索范围为空。返回 ans。
-
左边界(记录法)_参考代码
int check(int nums[], int L, int R, int x)
{
int mid,ans = -1;
while (L <= R) // 当左边界小于等于右边界时,继续查找
{
mid = (L + R) / 2; // 计算中间索引
if (nums[mid] == x) // 如果中间元素等于 x
{
ans = mid; // 记录可能的答案
R = mid - 1; // 因为是找左边界,则在左半部分继续查找
}
else if (nums[mid] > x) // 如果中间元素大于 x,则在左半部分继续查找
R = mid - 1;
else
L = mid + 1; // 如果中间元素小于 x,则在右半部分继续查找
}
return ans; // 如果循环结束仍未找到,则返回 ans
}
-
左边界(优化)_参考代码
因为找的是数的左边界,所以需要在 mid 的值的左区间继续寻找 5 ,只需在 nums[mid] >= x 时,让 R = mid(因为是 >= ,mid 可能是答案)。然后继续在 mid 及左区间继续找 5 。直到搜索范围为空,R 会停留在左边界就是答案。。
int check(int nums[], int L, int R, int x)
{
int mid;
while (L < R) // 当左边界小于右边界时,继续查找
{
mid = (L + R) / 2; // 计算中间索引
if (nums[mid] >= x) // 如果中间元素大于等于 x,则在左半部分继续查找
R = mid; // 因为 mid 可能是答案
else // 如果中间元素小于 x,则在右半部分继续查找
L = mid + 1;
}
if(nums[R] == x) return ans; // 如果 R 停留位置等于 x,返回 R
else return -1; // 否则返回 -1
}
-
x最靠右的位置_右边界
因为找的是数的右边界,所以需要在 mid 的值的右区间继续寻找 5 ,只需在 nums[mid] <= x 时,让 L = mid(因为是 <= ,mid 可能是答案)。然后继续在 mid 及左区间继续找 5 。直到搜索范围为空,L 会停留在左边界就是答案。。
int check(int nums[], int L, int R, int x)
{
int mid;
while (L < R) // 当左边界小于右边界时,继续查找
{
mid = (L + R + 1) / 2; // 计算中间索引(需向上取整)
if (nums[mid] <= x) // 如果中间元素小于等于 x,则在右半部分继续查找
L = mid; // 因为 mid 可能是答案
else // 如果中间元素大 x,则在左半部分继续查找
R = mid - 1;
}
if(nums[L] == x) return L; // 如果 L 停留位置等于 x,返回 L
else return -1; //则返回 -1
}
题目
认领作业后才可以查看作业内容。
- 状态
- 正在进行…
- 题目
- 3
- 开始时间
- 2024-1-1 0:00
- 截止时间
- 2099-12-31 23:59
- 可延期
- 0 小时