C语言链表二分查找代码未返回预期输出求助

你的代码存在几个关键问题，导致二分查找无法返回预期结果，下面逐一说明并给出修复方案：

1. 二分查找的核心前提缺失 #

二分查找仅适用于有序集合，但你使用insertAtBeginning插入元素，输入的10个整数会被逆序存储（比如输入1、2、3...10，链表实际是10->9->...->1），链表处于无序状态，直接导致二分查找逻辑完全失效。

2. 链表索引范围计算错误 #

计算链表长度时，你初始化r=0，遍历后r的值等于节点总数（10个节点时r=10），但链表的有效索引是0~9，后续计算mid可能取到10，此时for循环会让temp走到空指针，访问temp->data会触发未定义行为。

3. 查找失败的返回值错误 #

binarySearch函数最后返回l，但主函数是通过if(binarySearch(...))判断，非0值都会被判定为“找到”，这会导致未找到元素时也可能误判为“找到”，正确的失败返回值应为0。

修复后的完整代码 #

#include<stdio.h>
#include<stdlib.h>

// 链表节点结构
struct Node{
    int data;
    struct Node *next;
};

// 创建新节点
struct Node* newNode(int key){
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = key;
    temp->next = NULL;
    return temp;
}

// 插入到链表尾部，保留输入顺序
void insertAtEnd(struct Node **head, int key){
    struct Node* temp = newNode(key);
    if(*head == NULL){
        *head = temp;
        return;
    }
    struct Node* curr = *head;
    while(curr->next != NULL){
        curr = curr->next;
    }
    curr->next = temp;
}

// 链表冒泡排序，适配小规模数据
void sortLinkedList(struct Node **head){
    if(*head == NULL || (*head)->next == NULL) return;
    int swapped;
    struct Node *ptr1;
    struct Node *lptr = NULL;

    do{
        swapped = 0;
        ptr1 = *head;

        while(ptr1->next != lptr){
            if(ptr1->data > ptr1->next->data){
                // 交换节点数据
                int temp = ptr1->data;
                ptr1->data = ptr1->next->data;
                ptr1->next->data = temp;
                swapped = 1;
            }
            ptr1 = ptr1->next;
        }
        lptr = ptr1;
    }while(swapped);
}

// 二分查找实现
int binarySearch(struct Node* head, int key){
    if(head == NULL) 
        return 0;

    int l = 0, r = 0;
    struct Node* temp = head;
    // 计算链表长度，最终r为最后一个节点的索引
    while(temp != NULL){
        temp = temp->next;
        r++;
    }
    r--; // 修正索引范围为0~r

    while(l <= r){
        int mid = l + (r - l)/2;
        temp = head;
        // 移动到mid位置的节点
        for(int i=0; i<mid; i++){
            temp = temp->next;
        }
        if(temp->data == key) 
            return 1; // 找到返回1
        else if(temp->data > key) 
            r = mid - 1;
        else 
            l = mid + 1;
    }
    return 0; // 未找到返回0
}

int main(){
    struct Node* head = NULL;
    int key;

    printf("Enter 10 integers: \n");
    for(int i=0;i<10;i++){
        scanf("%d", &key);
        insertAtEnd(&head, key); // 插入到尾部保留输入顺序
    }

    sortLinkedList(&head); // 对链表排序，满足二分查找前提

    printf("Enter the element to be searched: ");
    scanf("%d", &key);

    if(binarySearch(head, key)) 
        printf("Element Found\n");
    else 
        printf("Element not Found\n");

    // 释放链表内存，避免泄漏
    struct Node* curr = head;
    while(curr != NULL){
        struct Node* next = curr->next;
        free(curr);
        curr = next;
    }

    return 0;
}

修复要点总结 #

• 将插入方式改为insertAtEnd保留输入顺序，新增sortLinkedList函数对链表排序，满足二分查找的有序要求。
• 修正链表索引范围计算，避免访问空指针。
• 统一查找失败的返回值为0，确保主函数判断逻辑正确。
• 添加链表内存释放代码，避免内存泄漏。

内容的提问来源于stack exchange，提问作者Eugeo