#include#include #include #include using namespace std;int rank1(int key, int *a,int length) { int lo = 0; int hi = length -1; int mid; while(lo <=hi) { mid= (lo+hi)/2; if(a[mid]==key) return mid; else if(a[mid]>key) hi=mid-1; else lo=mid+1; } return -1; }int main(){ srand((unsigned int) time(0)); int a[100]={0}; for(int i=0;i<100;i++) { a[i] = rand()%1000; } sort(a,a+100); a[99]=1001; int result =rank1(10, a, 100); cout< <
使用前提：待查找的数组必须是有序的，这里排序采用了STL的sort方法，主要是基于快速排序算法的，在之后的博客里我会陆续更新。
时间复杂度：O（lg n） 由于2的n次方为n
空间复杂度: 主要是数组本身的空间
基本思想：假设排序好的数组是升序。当我们想要查找对应key所在数组的位置时，每一次都与数组中间位置的值进行对比： 1. 如果数组中间值大于key那么，要找的值如果存在一定位于数组的前半部分，那么更新hi=mid-1；同时更新mid。
2.如果数组中间值小于key那么，要找的值如果存在一定位于数组的后半部分，那么更新low=mid+1；同时更新mid。
3. 如果mid对应的值等于key，那么返回mid就是要找的位置。
结束条件：1. 找到对应的位置 2.hi<low的时候