/*
 * 二分查找（有序序列的查找算法）
 * 核心思想：
 * 1)计算中值位置
 * 2)缩小查找位置
 **/
 
// 递归实现
int binary_search(int a[], int x, int left, int right)
{
    int mid;
    // 没找到
    if (left > right){
        return -1;
    }
    
    mid = (left + ringt) / 2;
    // 找到
    if (x == a[mid]){
        return mid;
    }
    
    if (a < a[mid]){
        return binary_search(a, x, left, mid-1);  // 排除右端，查找左端
    } else {
        return binary_search(a, x, mid+1, right);  // 反之
    }
}

// 非递归
int binary_search(int a[], int n, int x)
{
    int left, right, mid;  // 确定查找起点和终点
    left = 0;
    right = n - 1;
    while (left <= right){
        mid = (left + right) / 2;
        // 找到了
        if (x == a[mid]){
            return mid;
        }
        if(x < a[mid]){
            right = mid - 1;  // 排除右端，查找左端
        } else {
            left = mid + 1;  // 反之
        }
    }
    return -1;
}