算法学习笔记——二分

总结：二分思想适合通过比较key和arr[mid]，能够知道mid走向的情况，时间复杂度是O(logn)。

附二分及变种代码：

#include <iostream>
#include <vector>
using namespace std;

//题目描述：给定一个数组和一个key，找到第一个与key相等的元素的下标，要求时间复杂度O(logn)

//IN NULL FIND ANY OUT -1
//IN 1 2 3 4 FIND 5 OUT -1
//IN 1 2 3 FIND 1 OUT 0

int binary(const int *arr,const int len,const int key)
{
    if(arr == NULL || len <= 0)
        return -1;
    int left = 0;
    int right = len;
    int mid = left + (right - left)/2;
    vector<int> results;
    while(left <= right)
    {
        if(arr[mid] == key)
        {
            results.push_back(mid);
            //找最后一个跟key相等的数
            left = mid + 1;
            //找第一个跟key相等的数
            //left = mid + 1;
        }
        else if(arr[mid] > key)
        {
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
        mid = left + (left - right)/2;
    }
    if(results.size() == 0)
        return -1;
    else
        return results.back();
}

int main(void)
{
    int arr[5] = {1,2,3,4,5};
    cout<<binary(arr,5,2)<<endl;
    return 0;
};