node* searchid(long long id, node* L) {//按学号查找 node* p = L; while (p->next != NULL) {//遍历链表 if (p->next->id == id) { return p; } p = p->next; } return NULL; }将这个改为折半查找法

折半查找法（二分查找）是一种适用于有序数组的查找算法，因为链表并没有顺序，所以无法直接使用折半查找法。但可以对链表进行转换，将其转换成有序的数组，然后再使用折半查找法。这种转换需要额外的空间存储，时间复杂度也会有所增加。因此，这里我们不对链表进行转换，而是使用一种基于折半查找法的优化算法，称为“插值查找法”。

插值查找法的基本思想是根据查找值在数组中的大致位置，从而确定查找范围，从而提高查找效率。具体实现过程如下：

node* searchid(long long id, node* L) {
    node* left = L;
    node* right = NULL;

    // 先找到链表的尾节点
    while (L->next != NULL) {
        L = L->next;
    }
    right = L;

    while (left != right && left->next != right) {
        // 计算查找值在当前范围内的大致位置
        double pos = (double)(id - left->id) / (right->id - left->id);
        node* mid = left->next;
        // 根据位置比例，计算中间节点的位置
        for (int i = 0; i < (int)(pos * (right->id - left->id)); i++) {
            mid = mid->next;
        }

        if (mid->id == id) {
            return left;
        } else if (mid->id < id) {
            left = mid;
        } else {
            right = mid;
        }
    }

    if (left->next != NULL && left->next->id == id) {
        return left;
    }
    return NULL;
}

在这个函数中，我们使用了两个指针left和right，分别指向链表的头节点和尾节点。然后，通过计算查找值在当前范围内的大致位置，从而确定中间节点的位置。接着，根据中间节点的值和查找值的大小关系，缩小查找范围。最后，如果找到了目标节点，则返回其前一个节点的指针，否则返回NULL。

需要注意的是，插值查找法并不是适用于所有情况的最优算法，因为如果数据分布不均匀，可能会出现查找效率较低的情况。但是，对于数据分布均匀的链表，插值查找法可以提高查找效率。