Ошибка в алгоритме бинарного поиска для линейного списка

Question

Написал функцию бинарного поиска в линейном списке, каждая нода которого состоит из ключа(строка + целое) и данных. Сортирую список линейной сортировкой(для всех случаев сортировка срабатывает верно). Однако, есть какая-то ошибка в алгоритме поиска, что некоторые элементы находятся, а при поиске некоторых возникает ошибка связанная с памятью(segmentation fault), при попытке искать элементы которых нет в списке так же программа падает. Усложняется алгоритм тем, что нельзя как в массиве просто прыгать в середину, приходится "искусственно" туда попадать с помощью функции next. Вот сам код:

void binarysearch(struct List* _list, struct str_int key, struct Node* curNode){
    for(int i = 0; i < _list->size / 2 ; i++){
        curNode = next(curNode);
    }
    bool element_founded = false;
    if(_list->size > 0){
        if(strcmp(curNode->key.string, key.string) > 0){
            curNode = begin(_list);
            _list->size =_list->size - _list->size / 2;
            binarysearch(_list, key, curNode);
        }
        if(strcmp(curNode->key.string, key.string) < 0){
            _list->size =_list->size - _list->size / 2;
            binarysearch(_list, key, curNode);
        }
        if(strcmp(curNode->key.string, key.string) == 0){
            element_founded = true;
        }
    }
    if (element_founded == true) {
        printf("%s", "element founded");
        return;
    }
    if (_list->size == 0) {
        printf("%s", "element not founded");
        return;
    }
}

Подскажите, что нужно изменить или добавить для верной работы алгоритма.

Answer 1

Проблема решена, спасибо Stanislav Volodarskiy за идею.

struct Node* get_Item_by_index(struct List* list, int index){
    struct Node* curNode = begin(list);
    for (int i = 0; i < index; i++){
        curNode = next(curNode);
    }
    return curNode;
}
void binarysearch(struct List* _list, struct str_int key){
    bool element_found = false;
    int left = 0;
    int right = _list->size - 1;
    int mid = (_list->size + 0) / 2;
    while(left <= right){
        mid = (left + right) / 2;
        if (strcmp(key.string, get_Item_by_index(_list, mid)->key.string) == 0){
            element_found = true;
            printf("%s%d", "element found. it's position is ", mid);
            break;
        }
        if (strcmp(key.string, get_Item_by_index(_list, mid)->key.string) < 0){
            right = mid - 1;
        }
        else left = mid + 1;
    }
    if (element_found == false) printf("%s", "element not found");

}

БЛОГ НА HUSL

Ошибка в алгоритме бинарного поиска для линейного списка

Ответы (1 шт):