有序数组的二分查找

循环算法实现：

#include <iostream> using namespace std; //前闭后闭区间 int BinarySearch(int* array, int size, int data) { int left = 0; int right = size-1; int mid = 0; while(left <= right) { mid = left + ((right - left)>>1); if(array[mid] == data) return mid; //找到返回下标 else if(array[mid] > data) right = mid-1; else left = mid+1; } return -1; //未找到返回-1 } void FunTest() { int array[10] = {1,2,3,4,5,6,7,8,9,10}; int ret = BinarySearch(array, sizeof(array)/sizeof(array[0]), 7); cout<<ret<<endl; } int main() { FunTest(); system("pause"); return 0; }

递归算法实现：

#include <iostream> using namespace std; int BinarySearch(int* array, int left, int right, int data) { if(left <= right) { int mid = left + ((right - left)>>1); if(array[mid] == data) return mid; //找到返回下标 else if(array[mid] < data) return BinarySearch(array, mid+1, right, data); else return BinarySearch(array,left, mid-1, data); } } void FunTest() { int array[10] = {1,2,3,4,5,6,7,8,9,10}; int ret = BinarySearch(array, 0, (sizeof(array)/sizeof(array[0]))-1, 7); cout<<ret<<endl; } int main() { FunTest(); system("pause"); return 0; }