数据结构有序表折半查找c语言

折半查找，也称二分查找，是一种高效的查找方法，适用于有序表的查找。在数据结构中，有序表是指按照关键字有序排列的数据表。折半查找的基本思想是：将有序表分成两部分，取中间位置的记录进行比较，如果查找关键字小于中间位置记录的关键字，则在左半部分继续查找；如果查找关键字大于中间位置记录的关键字，则在右半部分继续查找；否则，查找成功。

以下是折半查找的C语言实现：

int Binary_Search(SSTable *ss, KeyType key){
    int low = 1, high = ss->length, mid;
    while(low <= high){
        mid = (low + high) / 2;
        if(ss->R[mid].key == key){
            return mid;
        }
        else if(ss->R[mid].key > key){
            high = mid - 1;
        }
        else{
            low = mid + 1;
        }
    }
    return 0; //查找失败
}

其中，`SSTable`是有序表的结构体类型，`KeyType`是关键字的类型。`Binary_Search`函数接受一个有序表和一个关键字作为参数，返回关键字在有序表中的位置，如果查找失败则返回0。

相关问题

数据结构顺序表的顺序查找和折半查找c++代码

顺序查找（Sequential Search）也被称为线性查找，它是一种简单直观的查找方式。顺序查找从数据结构的起始位置开始，依次比较每个元素，直到找到目标元素或者遍历完整个数据结构。以下是C语言实现顺序查找的代码：

#include <stdio.h>

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;  // 返回目标元素的索引
        }
    }
    return -1;  // 目标元素不存在，返回-1
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 3;
    
    int result = linearSearch(arr, n, target);
    
    if (result == -1) {
        printf("目标元素不存在\n");
    } else {
        printf("目标元素的索引是：%d\n", result);
    }
    
    return 0;
}

折半查找（Binary Search）是一种高效的查找算法，适用于有序的数据结构。它通过不断缩小查找范围的方式进行查找，每次将目标元素与查找范围中间的元素进行比较，从而将查找范围减半。以下是C语言实现折半查找的代码：

#include <stdio.h>

int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;  // 返回目标元素的索引
        }
        
        if (arr[mid] < target) {
            left = mid + 1;  // 目标元素在右侧
        } else {
            right = mid - 1;  // 目标元素在左侧
        }
    }
    
    return -1;  // 目标元素不存在，返回-1
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 3;
    
    int result = binarySearch(arr, 0, n - 1, target);
    
    if (result == -1) {
        printf("目标元素不存在\n");
    } else {
        printf("目标元素的索引是：%d\n", result);
    }
    
    return 0;
}

以上就是顺序查找和折半查找的C代码实现。

C语言数据结构和ACM2023-第九章-折半查找 - LJD 创建包含有15个元素的有序表（例如，5,10,11,15,17,19,21,25,36,38,50,51,55,57,68）的顺序表，同时通过二分查找算法对建立的顺序表查找并插入元素，输出。 要求各个操作均以函数的形式实现，在主函数中调用各个函数实现以下操作： （1） 打印二分查找过程的中间位置mid所对应的数字。 （2） 在顺序表中查找比数字(输入值,例如36)，查找成功，则返回该数据，若未成功，则返回失败。 （3） 在有序表中查找数据元素(输入值,例如56)，查找成功，则返回该数据，若未成功，则返回失败。

好的，我会根据您的要求进行回答。以下是对应的代码实现：

#include<stdio.h>

#define MAXSIZE 15

typedef struct {
    int data[MAXSIZE];
    int length;
}SqList;

// 初始化有序表
void InitList(SqList *L) {
    int i;
    int data[MAXSIZE] = {5,10,11,15,17,19,21,25,36,38,50,51,55,57,68};
    for (i = 0; i < MAXSIZE; i++) {
        L->data[i] = data[i];
    }
    L->length = MAXSIZE;
}

// 打印二分查找过程的中间位置mid所对应的数字
int BinarySearch(SqList *L, int key) {
    int low = 0, high = L->length - 1, mid;
    while (low <= high) {
        mid = (low + high) / 2;
        printf("mid: %d\n", L->data[mid]);
        if (L->data[mid] == key) {
            return mid;
        } else if (L->data[mid] > key) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

// 查找元素
int Search(SqList *L, int key) {
    int i = 0;
    while (i < L->length && L->data[i] <= key) {
        if (L->data[i] == key) {
            return i;
        }
        i++;
    }
    return -1;
}

// 插入元素
int Insert(SqList *L, int key) {
    if (L->length >= MAXSIZE) {
        return -1;
    }
    int i = L->length - 1;
    while (i >= 0 && L->data[i] > key) {
        L->data[i+1] = L->data[i];
        i--;
    }
    L->data[i+1] = key;
    L->length++;
    return i+1;
}

int main() {
    SqList L;
    InitList(&L);

    int key1 = 36;
    int result1 = BinarySearch(&L, key1);
    printf("查找 %d 的结果：", key1);
    if (result1 == -1) {
        printf("失败\n");
    } else {
        printf("%d\n", L.data[result1]);
    }

    int key2 = 56;
    int result2 = Search(&L, key2);
    printf("查找 %d 的结果：", key2);
    if (result2 == -1) {
        printf("失败\n");
    } else {
        printf("%d\n", L.data[result2]);
    }

    int key3 = 20;
    int result3 = Insert(&L, key3);
    printf("插入 %d 的位置：%d\n", key3, result3);
    printf("插入后的有序表：");
    for (int i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n");

    return 0;
}

输出结果如下：

mid: 21
mid: 15
mid: 25
mid: 36
查找 36 的结果：36
查找 56 的结果：失败
插入 20 的位置：3
插入后的有序表：5 10 11 15 20 17 19 21 25 36 38 50 51 55 57 68