main.cpp
#include <iostream> #include <cassert> #include <ctime> #include "MyUtil.h" using namespace std; // 二分查找法 template<typename T> int binarySearch(T arr[], int n, T target) { int l = 0, r = n - 1; // 在[l....r]的范围里,寻找target while (l <= r) { // 当 l == r时,区间[l....r]依然是有效的 int mid = (l + r) / 2; if (arr[mid] == target) return mid; if (target > arr[mid]) l = mid + 1; // target 在[mid+1....r]中 else // target < arr[mid] r = mid - 1; // target 在 [l....mid-1]中 } return -1; } int main() { int n = 1000000; int* data = MyUtil::generateOrderedArray(n); clock_t startTime = clock(); for (int i = 0; i < n; i++) assert(i == binarySearch(data, n, i)); clock_t endTime = clock(); cout<<"binarySearch test complete."<<endl; cout<<"Time cost:"<<double(endTime - startTime)/CLOCKS_PER_SEC<<" s"<<endl; return 0; }
MyUtil.h
#ifndef INC_STUDY_MYUTIL_H #define INC_STUDY_MYUTIL_H #include <iostream> #include <algorithm> #include <cassert> using namespace std; namespace MyUtil { int *generateOrderedArray(int n) { assert(n > 0); int *arr = new int[n]; for (int i = 0; i < n; i++) arr[i] = i; return arr; } } #endif
CMakeLists.txt
cmake_minimum_required(VERSION 3.14) project(study) set(CMAKE_CXX_STANDARD 14) add_executable(study main.cpp MyUtil.h)
二分查找法中,定义变量的区别:
int binarySearch(T arr[], int n, T target) { int l = 0, r = n; // 在[l....r)的范围里,寻找target while (l < r) { // 当 l == r时,区间[l....r)依然是无效的 int mid = l + (r - l) / 2; // 防止整型溢出的问题 if (arr[mid] == target) return mid; if (target > arr[mid]) l = mid + 1; // target 在[mid+1....r)中 else // target < arr[mid] r = mid; // target 在 [l....mid)中 } return -1; }