Реализовать бинарный поиск

Это мой бинарный поиск:

int binarySearch(int arr[], int value, int min, int max){
int pos = -1;

while (max >= min && pos == -1) {
int mid = (max+min)/2;

if(arr[mid] ==  value){
pos = mid;
}else if(arr[mid] < value){
min = mid +1;
}else if(arr[mid] > value){
max = mid -1;
}

}
return pos;
}

Я называю это так:

 //Arr contain values 0-63
int i = binarySearch(arr, 64, 0, 64);

Это средние значения

32 48 56 60 62 63 64

При последней проверке я пытаюсь получить доступ к элементу в позиции 64, когда последняя позиция в массиве равна 63.

Что не так с моей реализацией?

0

Решение

Ваш массив содержит значения от 0 до 63 (как вы упомянули), и вы даете следующие значения для min и max: min = 0, max = 64. И измените следующую строку, чтобы ваш код мог обрабатывать большие значения типа int, иначе есть вероятность переполнения памяти.

       int mid = min+(max-min)/2;

Приведенная выше формула упрощает до (max + min) / 2, но защищает целочисленное переполнение.

3

Другие решения

Когда max == min, ваша длина равна 0, поэтому вы не должны заходить в цикл. Изменить условие пока (max > min && ...) если ваш прилив «один за концом» (и ваш прилив, вероятно, должен быть «один за концом», это действительно полезная схема)

О, и сделай это max = mid вместо max = mid-1, поскольку max представляет «один за концом», а не последний элемент.

Как общее улучшение стиля кодирования, при выполнении такого рода кода повсюду утверждается, что ваши индексы находятся в пределах границ. Это может не только выявить проблемы раньше, но и помочь вам понять, какие значения находятся в границах, а какие нет …

0

Попробуйте этот код

while (max > min && pos == -1) {
int mid = (max+min)/2;

if(arr[mid] ==  value){
pos = mid;
}else if(arr[mid] < value){
min = mid;
}else if(arr[mid] > value){
max = mid;
}
}
0
По вопросам рекламы [email protected]