老师，麻烦您看下我的floor和ceil，简单测了下，好像没啥问题

Question

int floor(int arr[], int n, int val) // [l, r]中查找
{
int l = 0;
int r = n - 1;
int mid = l + (r - l) / 2;
while (l < r) {
if (arr[mid] > val)
r = mid - 1;
if (arr[mid] < val)
l = mid + 1;
if (arr[mid] == val && arr[mid] != arr[mid - 1])
return mid;
else if(arr[mid] == val && arr[mid] == arr[mid - 1])
r = mid - 1;
if (r == l + 1)
break;
mid = l + (r - l) / 2;
}
if (val >= arr[l] && val <= arr[r])
return l;
else if (val > arr[r])
return r;
else
return -1;
}
int ceil(int arr[], int n, int val)
{
int l = 0;
int r = n - 1;
int mid = l + (r - l) / 2;
while (l < r) {
if (arr[mid] > val)
r = mid - 1;
if (arr[mid] < val)
l = mid + 1;
if (arr[mid] == val && arr[mid] != arr[mid + 1])
return mid;
else if (arr[mid] == val && arr[mid] == arr[mid + 1])
l = mid + 1;
if (r == l + 1)
break;
mid = l + (r - l) / 2;
}
if (val > arr[l] && val <= arr[r])
return r;
else if (val <= arr[l])
return l;
else
return -1;
}

Answer 1

liuyubobobo 2025-02-04 23:57:42

我在课程中提供了 floor 和 ceil 的参考代码，可以参考。传送门：https://git.imooc.com/coding-71/coding-71/src/master/05-Binary-Search-Tree/Course%20Code%20%28C++%29/Optional-02-Floor-and-Ceil-in-Binary-Search/main.cpp

继续加油！：）