对分查找，也叫作二分查找（binary search）。

1. 问题描述

给定一个整数 X 和数组 A0，A1，A2….,AN-1，其中数组已经排好序，并存放在内存中，求使得 Ai=X 的下标 i ，若X 不在数组中，则返回 i=-1。

2. 题目分析

存放在内存中和不存放在内存中的区别？

对上述问题，如果我们预先了解过，就知道这种问题的时间复杂度是 O（logN），这是基于输入的数据都已经提前读入的前提而言的。因为如果输入的数据还没有读入，此时读入数据的时间复杂度是 O（N），O（N）>O（logN），忽略了分析事物的主要特征（就是忽视了算法的O（logN）的特点）。

3. 代码实现

方法一：从左到右扫描数据

没有利用数组已经排好序的条件，时间复杂度为O（N）

方法二：二分查找

代码如下：

#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[],int n,int X){
    int low=0;int high=n-1;
    while(low<=high){
        int mid=(low+high)/2;
        if(arr[mid]>X){
            high=mid-1;
        }else if(arr[mid]<X){
            low=mid+1;
        }else{
            return mid;
        }
    }
    return -1;
}
int main(){
    int arr[5]={-1,2,6,8,9};
    int n=5;
    for(int i=0;i<n;i++)
        cout<<binarySearch(arr,n,arr[i])<<endl;
}

有些人可能会疑惑，为什么 while中的条件（也就是最后的终止条件）要这么写，此时的终止条件我们可以代入一些比较“极端”的情况，比如：low=high，或者数组中的数都一样，从而判断终止条件是否能发挥作用，让程序正常结束运行。
在上文代码中，（high-low）max=n-1，（high-low）min=-1。

拓展成数据结构的一种方法

假如我们维护一个数据结构，使用二分查找的方法来查询该数据结构中的某个值，此时我们要求该数据结构应是有序的（最常见的形式就是有序数组）。也就是说

• 查询操作：O（logN）

为了维护数据的有序性，则：

• 插入操作：O（N）
• 书中说其他操作（增删改）也需要O（N），未验证。存疑。

所以该数据结构适用于组织那些相对稳定的（也就是插入、删除、修改不频繁的数据），比如元素周期表等。

习题 2.22

如果按照题目所说，不能正确运行。

其实这种情况也可以算是“极端情况”的一种，我们借此考虑边界条件的编写，保证程序的普适性和稳定性。

习题 2.23

1. 题意

实现对分查找使得在每次迭代中只有一个二路比较。

2. 分析

二路比较，开始的时候不明白什么意思，网上资料也很少，当查到了：对分查找时，我理解的 二路比较是迭代循环内只有两个比较，实现如下。

3. 代码实现

#include <bits/stdc++.h>
using namespace std;
bool binarySearch(int arr[],int n,int x){
    int low=0,high=n-1;
    int mid=(low+high)/2;
    while(low<=high&&arr[mid]!=x){
        if(arr[mid]<x){
            low=mid+1;
            mid=(low+high)/2;
        }else if(arr[mid]>x){
            high=mid-1;
            mid=(low+high)/2;
        }
    }
    if(low<=high){
        return true;
    }
    return false;
}
int main(){
    int arr[]={1,3,5,6,9};
    int n=5;
    for(int i=0;i<9;i++)
        cout<<binarySearch(arr,n,i)<<endl; 
}

这个代码和对分查找 在函数返回时条件略有不同，二者是等价的，请大家思考一下为什么。