二分查找及扩展
一、二分查找
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
template<typename T> int bin_search(const T data[], int left, int right, T target) { int mid; while (left <= right) { mid = (left + right) / 2; if (data[mid] > target) { right = mid - 1; } else if (data[mid] < target) { left = mid + 1; } else { return mid; } } return -1; } |
二、查找最后一个小于 n 的值
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// 查找第一个大于目标的元素 template<typename T> int bin_search_first_greater(const T data[], int left, int right, T target) { int mid; while (left <= right) { mid = (left + right) / 2; if (data[mid] > target) { if (mid == left || data[mid - 1] < target) return mid; right = mid - 1; } else { left = mid + 1; } } return -1; } |
三、查找第一个大于 n 的值
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
template<typename T> int bin_search_last_less(const T *data, int left, int right, T target) { int mid; while (left <= right) { mid = (left + right) / 2; if (data[mid] < target) { if (mid == right || data[mid + 1] > target) return mid; left = mid + 1; } else { right = mid - 1; } } return -1; } |
四、查找第一个等于 n 的值 [cra ... 阅读更多