Floor和Ceil

Question

老师，请问Floor和Ceil函数这样写的话会不会有什么没考虑到的地方。

#include "pch.h"
#include <iostream>
#include <cassert>
#include "BinarySearch.h"

using namespace std;

template<typename T>
int floor(T arr[], int n, int target) {
	int l = 0, r = n - 1;
	int pos = -1;

	while (l <= r) {
		int mid = (r - l) / 2 + l;
		if (arr[mid] == target) {
			pos = mid;
			r = mid - 1;
		}
		else if (arr[mid] > target)
			r = mid - 1;
		else
			l = mid + 1;
	}

	if (pos == -1)
		pos = r;

	return pos;
}

template<typename T>
int ceil(T arr[], int n, int target) {
	int l = 0, r = n - 1;
	int pos = -1;

	while (l <= r) {
		int mid = (r - l) / 2 + l;
		if (arr[mid] == target) {
			pos = mid;
			l = mid + 1;
		}
		else if (arr[mid] > target)
			r = mid - 1;
		else
			l = mid + 1;
	}

	if (pos == -1)
		pos = l;

	return pos;
}

int main() {

	int a[] = { 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 5, 5, 5, 6, 6, 6 };
	int n = sizeof(a) / sizeof(int);
	for (int i = 0; i <= 8; i++) {

		int floorIndex = floor(a, n, i);
		cout << "the floor index of " << i << " is " << floorIndex << ".";
		if (floorIndex >= 0 && floorIndex < n)
			cout << "The value is " << a[floorIndex] << ".";
		cout << endl;

		int ceilIndex = ceil(a, sizeof(a) / sizeof(int), i);
		cout << "the ceil index of " << i << " is " << ceilIndex << ".";
		if (ceilIndex >= 0 && ceilIndex < n)
			cout << "The value is " << a[ceilIndex] << ".";
		cout << endl;

		cout << endl;
	}
}

Answer 1

liuyubobobo 2020-01-06 00:57:04

目测没问题：）

不过 floor 和 ceil 的求解可以不依靠 pos，只靠 l 和 r 得到。我在这个课程的补充代码中提供了一个参考代码，有兴趣可以参考：）

传送门：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/05-Binary-Search-Tree/Course%20Code%20(C%2B%2B)/Optional-02-Floor-and-Ceil-in-Binary-Search/main.cpp

继续加油！：）