二分查找

一、基本思想

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

算法过程：
1.每次查找取数组中位数的值进行比较，
2.如果目标值值大于中位数的值，则截取中位数右侧的数组再次进行二分查找，
3.如果目标值小于中位数的值，则截取中位数左侧的数组再次进行二分查找，
4.直到找到相对应的中位数才终止查找算法。
5.每经过一次比较，查找范围就缩小一半。

二、实现

递归实现

#include <iostream>

int binarySearch(int array[], int low, int high, int value) { //使用递归方式进行二分查找 
    if(low > high) { //递归结束条件 
        return -1;
    }
    
    int mid = (low + high) / 2; //取中间位置 
    if(array[mid] == value) { //如果中间位置的值等于要查找的值，则返回中间位置 
        return mid;
    } else if(array[mid] < value) { //如果中间位置的值小于要查找的值，则对右子序列进行递归查找 
        return binarySearch(array, mid+1, high, value); 
    } else { //如果中间位置的值大于要查找的值，则对左子序列进行递归查找 
        return binarySearch(array, low, mid-1, value);
    }
} 

int main(int argc, char** argv) {
    int array[] = {14, 17, 19, 21, 25, 25, 29, 30}; 
    int value = 29; 
    int index = binarySearch(array, 0, 7, value);
    printf("search %d, index: %d\n", value, index);
    printf("\n");
    return 0;
}

非递归实现

#include <iostream>

int binarySearch(int array[], int n, int value) { //使用迭代方式进行二分查找 
    int low = 0;
    int high = n - 1;
    while(low <= high) { //循环条件为low小于等于high
        int mid = (low + high) / 2; //取中间位置 
        if(array[mid] == value) { //如果中间位置的值等于要查找的值 
            return mid;
        } else if(array[mid] < value) { //如果中间位置的值小于要查找的值 
            low = mid + 1;
        } else { //如果中间位置的值大于要查找的值 
            high = mid - 1;
        }
    }
} 

int main(int argc, char** argv) {
    int array[] = {14, 17, 19, 21, 25, 25, 29, 30}; 
    int value = 29;
    int index = binarySearch(array, 8, value);
    printf("search %d, index: %d\n", value, index);
    printf("\n");
    return 0;
}