二分查找法

一、基本思路

#include <iostream>
#include <cassert>
#include <ctime>

using namespace std;

template<typename T>
int binarySearch(T arr[], int n, T target){
    int l = 0, r = n-1;
    while( l <= r ){
        int mid = l + (r-l)/2;
        if( arr[mid] == target )
            return mid;
        if( arr[mid] > target )
            r = mid - 1;
        else
            l = mid + 1;
    }
    return -1;
}
//测试代码
int main() {
    int n = 1000000;
    int* a = new int[n];
    for( int i = 0 ; i < n ; i ++ )
        a[i] = i;
    clock_t startTime = clock();
    for( int i = 0 ; i < 2*n ; i ++ ){
        int v = binarySearch(a, n, i);
        if( i < n )
            assert( v == i );
        else
            assert( v == -1 );
    }
    clock_t endTime = clock();
    cout << "Binary Search (Without Recursion): " << double(endTime - startTime) / CLOCKS_PER_SEC << " s"<<endl;
    delete[] a;
    return 0;
}

二、leetcode有关题型：

704-二分查找

思路：纯二分查找

 69-x的平方根

思路：理解根为以x为最右的区间值的查找

 35-搜索插入位置

思路：理解为找到左边为最大值的插入位置

153-寻找旋转排序数组中的最小值

思路：可以设置最小值为最右边界值，然后二分查找到该值

154-

思路：153题的升级版，需要考虑重复元素的存在，可以考虑去除重复后继续查找

287-寻找重复数

思路：求出mid值后，统计所有小于mid的重复值个数，然后统计值比mid小就在右2半区间，否则就在左半区间，此时的最右值就是我们要求的答案

1095-山脉数组中查找目标值

思路：先二分查找找出最大值，然后再分左右两边查找目标值，使用三次二分查找

/**
 * // This is the MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * class MountainArray {
 *   public:
 *     int get(int index);
 *     int length();
 * };
 */
class Solution {
public:
    int findInMountainArray(int target, MountainArray &mountainArr) {
        int l = 0, r = mountainArr.length() - 1;
        
        while (l < r) {
            int mid = l + (r - l)/2;
            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
    
        int peak = l;
        if (target > mountainArr.get(peak)) return -1;
    
        // 先找左边
        l = 0, r = peak;
        while (l <= r) {
            int mid = l + (r - l)/2;
            if (target == mountainArr.get(mid)) {
                return mid;
            } else if (target < mountainArr.get(mid)) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
    
        // 在右边找。
        l = peak + 1, r = mountainArr.length() - 1;
        while (l <= r) {
            int mid = l + (r - l)/2;
            if (target == mountainArr.get(mid)) {
                return mid;
            } else if (target > mountainArr.get(mid)) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
    
        return -1;
    }
};