算法学习之二分查找法

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;
}