二进制搜索升序排列C++

问题描述：

我想在数组升序时使用二进制搜索算法搜索数组。我不知道为什么每次我搜索一个值时它说它不在数组中......这是我的代码。二进制搜索升序排列C++

int main() 
{ 
    int found, value; 
    int array[] = {0,2,2,3,5,9,11,12,12,12,13,17,18,19,19,34}; // array to be searched 

    cout << "Enter an integer to search for:" << endl; 
    cin >> value; 

    found = binarySearch(array, SIZE, value); //function call to perform the binary search 
               //on array looking for an occurrence of value 
    if (found == -1) 
     cout << "The value " << value << " is not in the list" << endl; 
    else 
    { 
     cout << "The value " << value << " is in position number " 
      << found + 1 << " of the list" << endl; 
    } 
    system("pause"); 
    return 0; 
} 

//**********BINARY SEARCH********** 
int binarySearch(int array[],int numElems,int value) //function heading 
{ 
    int first = 0;     // First element of list 
    int last = numElems - 1;  // last element of the list 
    int middle;      // variable containing the current 
            // middle value of the list 

    while (first <= last) 
    { 
     middle = first + (last - first)/2; 

    if (array[middle] == value) 
     return middle;    // if value is in the middle, we are done 

    else if (array[middle] < value) 
     last = middle - 1;   // toss out the second remaining half of 
            // the array and search the first 
    else 
     first = middle + 1;  // toss out the first remaining half of 
            // the array and search the second 
    } 

    return -1;      // indicates that value is not in the array 
}

'std :: lower_bound'可能会有所帮助。 – Jarod42

正如我在你的另一个问题上指出的那样，在SO上不允许破坏问题甚至你自己的问题。订阅者内容[在您发布后由SO拥有]（https://meta.stackoverflow.com/questions/336993/op-accepts-answer-then-vandalizes-the-question/）。 – azurefrog

答

您的条件二进制搜索反转。

if array[middle] < value然后你想在上半部分而不是下半部分搜索你的元素。

谢谢！这工作！它总是那些小东西.... – user3408267

答

交易所last = middle - 1和first = middle + 1和二进制搜索将正常工作。

让搜索7

2 3 5 6 [7] 8 8 9

0 1 2 3 4 5 6 7

^f .... ^m ............ ^l

m = (7 + 0)/2 = 3

索引3的元素是6. 6 < 7。那么我们应该将first更改为mid + 1。

如果中期值小于搜索值，那么我们就应该改变first，所以搜索该值仍处于区间[first; last]

二进制搜索升序排列C++

相关推荐