二分查找 是个经典的问题 但是 考虑到很多边界条件 能在短时间的面试环节 写出个零bug版本 还是需要多code
本人总结了自己写的三个版本 递归与非递归
另外参考了编程之美的写法 一般人的写法 while循环体有2次的比较 而这里第三种写法 while循环体只有1次的比较
虽然两者算法复杂度为O(lgn) 但是常数因子有了极大的提升 建议参考最优的二分查找写法
#include <iostream> using namespace std; /** 二分查找 * * key 待查找元素 * begin 数组起始位置 * end 数组结束位置 * 返回值为待查找的元素在数组位置 若找不到 则返回-1 * */ int BinarySearch(int array[], int begin, int end,int key) { while(begin<=end) { int mid=begin+(end-begin)/2; if(array[mid]==key) {return mid;} else if (array[mid]>key) {return BinarySearch(array,begin,mid-1,key);} else {return BinarySearch(array,mid+1,end,key);} } return -1; } int BinarySeachNonRecursive(int array[], int begin, int end,int key) { int mid; while(begin<=end) { mid=begin+(end-begin)/2; if(array[mid]==key) {return mid;} else if (array[mid]>key) {end=mid-1;} else {begin=mid+1;} } return -1; } // 最优二分查找写法 int BinarySeachOptimal(int array[], int begin, int end,int key) { int mid; while(begin<end-1) { mid=begin+(end-begin)/2; //防止溢出 if(array[mid]<=key) { begin=mid; } else{ end=mid; } } if(array[end]==key) { return end; } if(array[begin]==key) { return mid; } return -1; } int main() { int num; cin >> num; int array[num]; for(int i=0;i<num;i++) { cin >> array[i]; } int key; cin >> key; //int index=BinarySearch(array,0,num-1,key); //int index=BinarySeachNonRecursive(array,0,num-1,key); int index=BinarySeachOptimal(array,0,num-1,key); if(index>=0) { cout << "the index of "<< key << " is "<< index<<endl; } else{ cout << key << " is not found in the array"<<endl; } //cout << "Hello world!" << endl; return 0; }