Как реализовать двоичный поиск для массива целых чисел?

Question

Я хочу реализовать двоичный поиск для массива целых чисел. Я убедился, что массив отсортирован пошагово. Но моя функция не отслеживает все случаи, и некоторые из проверок терпят неудачу. Что мне здесь не хватает? Value обозначает целое число, которое я пытаюсь найти.

bool search(int value, int array[], int n) 
{ 
    int left = 0; 
    int right = n - 1; 
    int middle = (left + right)/2; 

while (right >= left) 
{ 
    if (array[middle] == value) 
    return true; 
    else if (array[middle] < value) 
    right = middle; 
    else if (array[middle] > value) 
    left = middle + 1; 

    middle = (left + right)/2; 
} 

return false; 
} 

Я предполагаю, что некоторые левые или правые граничные случаи не прогнозируются. Я также не сильный относительно while состояние.

Answer 1

Вы смешанный левый и правый, если array[middle] < value вы должны изменить left.

bool search(int value, int array[], int n) 
{ 
    int left = 0; 
    int right = n - 1; 
    int middle = left + (right - left)/2; 

    while (right >= left) 
    { 
     if (array[middle] == value) 
      return true; 
     else if (array[middle] > value) 
      right = middle - 1; 
     else if (array[middle] < value) 
      left = middle + 1; 

     middle = (left + right)/2; 
    } 
    return false; 
} 

будет работать: http://ideone.com/VSAhnZ

Дальнейшие улучшения могут быть:

1. Вы можете исключить middle в else части, потому что вы уже доказали, что это не правильное значение (right = middle; =>right = middle - 1;)

2. Второй else if может быть заменен на else. Если это не значение и не меньше, вам не нужно проверять, больше ли он.

Answer 2

Стандартный алгоритм бинарного поиска можно найти в любом месте. но только исправление кода:

bool search(int value, int array[], int n) 
{ 
    int left = 0; 
    int right = n - 1; 
    int middle; 
    while (left <= right) 
    { 
     middle = (left + right)/2;  
     if (value > array[middle]) 
      left = middle + 1; 
     else if (value < array[middle]) 
      right = middle - 1;     
     else 
      return true; 
    } 
    return false; 
}