Бинарный поиск в C++: по возрастанию + по убыванию упорядоченные массивы

Question

Так что я пытаюсь сделать двоичный алгоритм сортировки для моего класса C++, но я продолжаю получать ошибку сегментации, когда запускается моя функция binarySearch. Независимо от того, как сильно я и мой сосед по комнате смотрят на это, мы не можем найти проблему. Любая помощь будет принята с благодарностью.

int binarySearch(int arr[], int k, int first, int last) 
{ 
    if(arr[first] <= arr[last]) 
    { 
     int mid = (first + last)/2; 

     if(k == arr[mid]) 
     { 
      return mid; 
     } 
     else if (k < arr[mid]) 
     { 
      return binarySearch(arr, k, first, mid-1); 
     } 
     else return binarySearch(arr, k, mid+1, last); 
    } 
    else if(arr[first] >= arr[last]) 
    { 
     int mid = (first + last)/2; 

     if(k == arr[mid]) 
     { 
      return mid; 
     } 
     else if (k < arr[mid]) 
     { 
      return binarySearch(arr, k, mid+1, last); 
     } 
     else return binarySearch(arr, k, first, mid-1); 
    } 
    else return -1; 
} 

После фиксации ошибки сегментации, я заметил, что я должен иметь ошибку где-то в моей логике, так как программа поддерживает вывод о том, что ключ не удалось найти, даже если она существует в массиве.

Answer 1

Ваш код работает на самом деле, если элемент, который вы ищете в массиве. Однако он не обнаруживает неверный ввод.

При вызове функции, убедитесь, что:

• first и last между 0 и (длина массива - 1)
• first < last

например: если массив имеет 10 элементов , первая и последняя должны быть между 0 и 9.

Пробег this:

int main() { 
    int a[] = {134, 232, 233, 234, 587, 623, 793, 802, 963, 1074}; 
    int b[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; 
    int na = binarySearch(a, 587, 0, 9); 
    int nb = binarySearch(b, 3, 0, 9); 

    printf("na: %d\n", na); // prints 'na: 4' 
    printf("nb: %d\n", nb); // prints 'nb: 7' 
} 

Если элемент, который вы ищете это не в массиве, то рекурсия не делает и не кончить, можно исправить, добавив следующие главы binarySearch():

if (first == last && k != arr[first]) 
    return -1; 

Answer 2

не является основной проблема, но, чтобы предотвратить переполнение это обычно переписать int mid = (first + last)/2; в int mid = first + (last-first)>>1; Кроме того, кажется, что вы никогда не ударите по линии return -1 (первые два условным заботиться обо всех возможных порядков)

реализация (для строго возрастает или уменьшается массив) может выглядеть следующим образом, что

#include <cassert> 

int binarySearch(int* array, int k, int l, int h, bool asc) 
{ 
    if (l>h) 
     return -1; 
    int m = l + ((h - l) >> 1); 
    if (array[m] == k) 
     return m; 
    else 
    { 
     if (array[m]>k) 
      return binarySearch(array, k, (asc ? l : m + 1), (asc ? m - 1 : h),asc); 
     else 
      return binarySearch(array, k, (asc ? m + 1 : l), (asc ? h : m - 1),asc); 
    } 
} 

int main() 
{ 
    int ascArray[7] = {1, 2, 3, 4, 5, 6, 7}; 
    int descArray[7] = {7, 6, 5, 4, 3, 2, 1}; 
    assert(binarySearch(ascArray, 7, 0, 6, ascArray[0] < ascArray[1]) == 6); 
    assert(binarySearch(descArray, 7, 0, 6, descArray[0] < descArray[1]) == 0); 
} 

Answer 3

вместо того, чтобы использовать, если еще, если вы можете попробовать во время цикла:

int mid = (first + last)/2; 
while(first<=last && arr[mid]!=k){ 
    if(arr[mid]<k) 
     first=mid+1; 
    else 
     last=mid-1; 
    mid = (first + last)/2; 

} 
if(arr[mid] == k){ 
    std::cout<<"Found"<<std::endl; 
}else{ 
    std::cout<<"Not Found"<<std::endl; 
} 

вместо этого вы можете использовать вектор, что составляет это очень просто:

#include <iostream> 
#include <vector> 
#include <algorithm> 
using namespace std; 

int main(){ 

int arrint[] = {3,5,2,1,7,6,9,4,8,10}; 
vector<int> vector1(arrint,arrint+10); 

sort(vector1.begin(),vector1.end()); 
int n; 
cout<<"Enter element to search: "; 
cin>>n; 
cin.ignore(); 
cout<<endl; 

if(binary_search(vector1.begin(),vector1.end(),n)){ 
    cout<<"Found: "<<n<<endl; 
}else{ 
    cout<<n<<" Not Found"<<endl; 
} 


//cin.get(); 
return 0; 
} 

Answer 4

Удостоверьтесь, что first>=last. Я думаю, что авария связана с тем, что вы не находите элемент в массиве.