二进制搜索不能使用向量工作

Question

我有我的二进制搜索功能的问题。基本上只是想检查向量中是否有零。但它不会返回正确的结果。这里是代码。任何人都可以弄清楚我做错了什么？

bool RecursiveBinarySearch::binarySearch(std::vector<int> &input, int left, int right) 
{ 
    int mid_number; 
    int odd_even = (right - left)%2; 
    if(odd_even == 0) 
    { 
     mid_number = (right-left)/2; 
    } 
    else 
    { 
     mid_number = (((right-left)+1)/2)-1; 
    } 

    if(right>=left) 
    { 
     if(input.at(mid_number)==0) 
     { 
      return true; //mid_number 
     } 
     else if(input.at(mid_number)>0) 
     { 
      return binarySearch(input, left, mid_number-1); 
     } 
     else 
     { 
      return binarySearch(input, mid_number+1, right); 
     } 
    } 
    else 
    { 
     return false; //-1 return 
    } 
} 

输入：1 2 3 4 0则它应该返回真实的，但返回0
输入：1 0应返回true，而返回false。

Answer 1

您的mid_number是错误的。

考虑binarySearch(arr, 5, 11)。您正在将mid_number设置为3.但是3不在[5,11)的范围内。您需要将left添加到mid_number。