一、基本思想
二分查找也称折半查找（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;
}
