Реализовать бинарный поиск
Это мой бинарный поиск:
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 до 63 (как вы упомянули), и вы даете следующие значения для min и max: min = 0, max = 64. И измените следующую строку, чтобы ваш код мог обрабатывать большие значения типа int, иначе есть вероятность переполнения памяти.
int mid = min+(max-min)/2;
Приведенная выше формула упрощает до (max + min) / 2, но защищает целочисленное переполнение.
Другие решения
Когда max == min, ваша длина равна 0, поэтому вы не должны заходить в цикл. Изменить условие пока (max > min && ...) если ваш прилив «один за концом» (и ваш прилив, вероятно, должен быть «один за концом», это действительно полезная схема)
О, и сделай это max = mid вместо max = mid-1, поскольку max представляет «один за концом», а не последний элемент.
Как общее улучшение стиля кодирования, при выполнении такого рода кода повсюду утверждается, что ваши индексы находятся в пределах границ. Это может не только выявить проблемы раньше, но и помочь вам понять, какие значения находятся в границах, а какие нет …
Попробуйте этот код
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;
}
}