二分查找

原理

二分查找顾名思义，就是把序列分成两半进行查找。

另外，二分查找要求线性表必须使用顺序结构存储，并且容器内部元素排列有序。

为了方便，本文的序列都是以升序为例（可有重复元素，返回第一个符合条件的索引值）

假设任意递增有序序列 A，和要查询的值t

首先找到中间值的索引mid，其中l为序列第一个元素的索引，r为最后一个元素的索引。之所以此处不给出 $\lfloor(r+l)/2 \rfloor$ 的形式，是因为在编写程序时这种算法可能会溢出。

$$ mid(l,r) = l + \lfloor(r-l)/2 \rfloor $$

然后比较该位置值与所查询值的大小，这样就分成了三种情况：

当值相等时，mid即我们要的索引值
当t小于mid位置的元素时（注意是元素），在左半序列找查，获取左半序列的中间值索引（如下公式），然后重复比较，直到mid位置处的元素为我们所查找的元素。如果直到子序列长度为0都未找到，则说明序列A不存在该元素t，应停止查找。

$$ mid(l,mid(l,r)) $$

当t大于mid位置的元素时，在右半序列找查，获取右半序列的中间值索引（如下公式），然后重复比较，直到mid位置处的元素为我们所查找的元素。如果直到子序列长度为0都未找到，则说明序列A不存在该元素t，应停止查找。

$$ mid(mid(l,r)+1,r) $$

现在假设序列A以及要找查元素t的值如下，第一个元素的索引为0，最后一个元素的索引为4

$$ A = \{1,2,3,4,5\}, \space t=2 $$

序列中间元素索引为2，对应元素值为3。

比较t与2的值，有

$$ t < 2 $$

则向左半序列查找，记A的左半序列如下

$$ A_{left} = \{1,2,3\} $$

再取中间元素的索引为1，比较t与$A_{left}[1]$的值，发现相等，则1即为我们所查询的元素的索引值。

代码实现

代码实现分为递归与非递归两种形式。

递归

/*二分查找，未找到则返回false；找到返回true，并将结果传入index
* arr: 要被查询的有序数组
* l: 查询序列最左的元素的索引
* r: 查询序列最右的元素的索引
* target: 要查询的元素
* index: 返回的结果
 */
bool BinSearch(int arr[], int l, int r, int target, int& index)
{
    if (l >= r)
    {
        if (target == arr[l])
        {
            index = l;
            return true;
        }
        index = -1;
        return false;
    }

    int mid = l + (r - l) / 2;

    if (target > arr[mid])
        return BinSearch(arr, mid + 1, r, target, index);
    else
        return BinSearch(arr, l, mid, target, index);
}

非递归

/*二分查找，未找到则返回false；找到返回true，并将结果传入index
* arr: 要被查询的有序数组
* l: 查询序列最左的元素的索引
* r: 查询序列最右的元素的索引
* target: 要查询的元素
* index: 返回的结果
 */
bool BinSearch(int arr[], int l, int r, int target, int& index)
{
    while (l < r)
    {
        int mid = l + (r - l) / 2;
        if (arr[mid] >= target)
            r = mid;
        else
            l = mid + 1;
    }
    if (arr[l] == target)
    {
        index = l;
        return true;
    }
    else
    {
        index = -1;
        return false;
    }
}

二分查找