Двоичный поиск по возрастанию Array C++

Question

Я пытаюсь найти массив, используя алгоритм бинарного поиска, когда массив находится в порядке возрастания. Я не знаю, почему каждый раз я ищу значение, которое говорит, что это не в массиве ... Вот мой код.

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 
} 

Answer 1

вашего состояния для бинарного поиска инвертируется.

Если array[middle] < value, то вы хотите найти свой элемент в верхней половине, а не в нижней половине.

Answer 2

Обмен 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]