二分查找法

一.介绍

二分查找法是一种在计算机中快速查找相应内容的算法，它基于有序数组将其查找，在计算机中广泛使用，已经成为计算机中必不可少的算法，二分查找: 又称为 折半查找,二分查找,适合对已经排序好的数据集合进行查找,时间复杂度O(log2n),效率高。

二.逻辑

假设有一升序的数据集合{0, 1, 2, 3, 4, 5, 6, 7, 8}先找出升序集合中最中间的元素mid = 4,将数据集合划分为两个子集,将最中间的元素mid = 4和关键字key进行比较，如果等于key则返回，如果大于关键字key，则在前一个数据集合中查找，否则在后一个子集中查找，直到找到为止，如果没找到则返回-1

例如：

{0, 1, 2, 3, 4, 5, 6, 7, 8}，我们需要查找元素3，第一次会把该数组一分为二

找到最中间的数mid = 4；将mid和3比较，此时发现mid > 3;所以会进入数组{0, 1, 2, 3,}（一共4个元素，我们需要找到索引（r+l)/2 的元素1.5，我们将其设置为整型所以就是查找到1）然后将mid = 1和3比较，此时mid < 3,所以会进入{2, 3}

仍然是mid =（r+l) / 2 ,最后就找到了元素3。

三.代码

下面用c++代码实现

#include<iostream>
using namespace std;
//使用模板函数
template <typename T >
//将索引为target的元素arr[target]
int BinraySearch(T arr[], int n, int target)
{
    int l = 0;
    int r = n - 1;
    while(l<=r) {
        //int mid = (l+r)/2; 一分为二，但是这里可能存在溢出，所以用下面的优化版本 
        int mid = l - (l + r) / 2;
        if (arr[target] == arr[mid]) {
            return mid;
        }
        else if (arr[target] > arr[mid]) 
        {
            r = mid + 1;
        }else  
            //arr[target] < arr[mid];
            l = mid - 1;
    }
    //如果查找元素不存在，则返回-1return -1;
}