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

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。