二分查找

二分查找也叫折半查找，它只对有序的序列有效。二叉查找的基本步骤是：

1. 首先保证序列是有序的，这里以从小到大的顺序为例，定义序列开始位置和结束位置的值为low和high
2. 找到序列的中间点mid，比较mid和待查找值key的大小，如果mid>key，就查找mid前的部分（low~mid），否则查找mid后的部分（mid~high）
3. 重复上述步骤，直到找到一个值等于key，或者low>=high即key在序列中不存在

int binarySearch(const int *arr, int array_size, int key)
{
    int low = 0, high = array_size - 1, mid;

    while (low <= high)
    {
        mid = (low + high) / 2;

        if (arr[mid] == key)
            return mid;
        if (arr[mid] > key)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

遍历查找的时间复杂度是O(n)，二分查找则是O(logn)。因此在有序序列上，使用二分查找的效率比较高。