尝试数据结构中的binsearch无反应

Question

最近在学数据结构和算法，靠印象敲了里面的代码时:想模拟有序向量的查找，终端没反应，是时间太久还是没跳出循环？

#include<iostream>
using namespace std;
template <typename T>
int binsearch(T*A,T const &e,int low,int high)
{
    while(low<high)
    {
        int mi=(low+high)/2;
        (e<A[mi])?high=mi:low=mi;
    }
    return --low;
}
int main()
{
    int num[]={1,5,8,13,19,28,35,89,99,100};
    int k=13;
    cout<<binsearch(num,k,0,10)<<endl;
}

Answer 1

因为你的问题并不满足二分搜索的分治思想，分治思想需要保证每一步分治之后问题规模的缩小，
在你的代码中，计算mid=(lo+hi)/2这一步时，如果mid的计算结果等于lo，并且A[mid]等于e时，那么问题的规模并不会缩小，而是会陷入死循环
而实际上在正确的二分搜索中，不论A[mid]是否与e相等，问题的规模一定会缩小，并且子问题的结构必须要和父问题保持一致性