C语言数据结构折半查找（二分查找）-创新互联

也称二分查找，它是一种效率较高的查找方法，但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

查找过程：
从表的中间记录开始，如果给定值和中间记录的关键字相等，则查找成功；如果给定值大于或者小于中间记录的关键字，则在表中大于或小于中间记录的那一半中查找，这样重复操作，直到查找成功，或者在某一步查找区间为空，则代表查找失败。

折半查找每一次查找都使查找范围缩小一半，与顺序查找相比，很显然会提高查找效率。

typedef int KeyType ;

typedef struct {KeyType key;        //关键字域
}ElemType;

typedef struct {ElemType *R;        //存放查找表中元素的数组
    int length;         //记录查找表中的长度
}SSTable;

void Create_List(SSTable *ss){int length;
    printf("请输入元素个数：");
    scanf("%d",&length);
    ss->length = length;
    ss->R = (ElemType *)malloc((length + 1) * sizeof(ElemType)); //分配内存
    printf("请依次输入元素：");
    for(int i = 1;i<= length;i++){scanf("%d",&ss->R[i].key);
    }
}

由于上面写的表并非是顺序表，而且为了程序的开放性，设定多一个排序，给表排序。这里利用冒泡排序。

冒泡排序：
是一种最简单的交换排序方法，它通过两两比较相邻记录的关键字，如果为逆序，则进行交换，从而使关键字小的记录如气泡一般逐渐往上“漂浮”，或者使关键字大的记录如石头一般逐渐往下沉。

void Bubble(SSTable *ss,int length){printf("排序后的结果：");
    ss->R[0] = ss->R[1];//哨兵初始值
    for(int i=0;i//冒泡排序，循环遍历
        for(int j=1;jif(ss->R[j].key >ss->R[j+1].key) {//交换数值
                int temp;
                temp=ss->R[j].key;
                ss->R[j].key=ss->R[j+1].key;
                ss->R[j+1].key=temp;
            }
        }
    }
    for(int i = 1;i<= ss->length;i++){printf("%d  ",ss->R[i].key);
    }
}

最后输出排序结果，检验。

置查找区间初值，low为1，high为表长。

当low<=high 时，循环执行：
mid取low和high的中间值；
将给定值x与中间位置记录的关键字进行比较，若相等则查找成功，返回中间位置mid；
若不相等，则利用中间位置记录将表对分前、后两个子表。

唯一注意的是，循环条件是 low<=high，而不是low

int Search(SSTable *ss,int x){int low = 1,high,mid;
    high = ss->length;
    while (low<= high){mid = (low + high) / 2;
        if (ss->R[mid].key == x){return mid;
        }
        else if (ss->R[mid].key< x){low = mid;
        }
        else if(ss->R[mid].key >x){high = mid;
        }
    }
}

#include#includetypedef int KeyType ;

typedef struct {KeyType key;        //关键字域
}ElemType;

typedef struct {ElemType *R;        //存放查找表中元素的数组
    int length;         //记录查找表中的长度
}SSTable;

//创建查找表
void Create_List(SSTable *ss){int length;
    printf("请输入元素个数：");
    scanf("%d",&length);
    ss->length = length;
    ss->R = (ElemType *)malloc((length + 1) * sizeof(ElemType)); //分配内存
    printf("请依次输入元素：");
    for(int i = 1;i<= length;i++){scanf("%d",&ss->R[i].key);
    }
}

//排序
void Bubble(SSTable *ss,int length){printf("排序后的结果：");
    ss->R[0] = ss->R[1];//哨兵初始值
    for(int i=0;i//冒泡排序，循环遍历
        for(int j=1;jif(ss->R[j].key >ss->R[j+1].key) {//交换数值
                int temp;
                temp=ss->R[j].key;
                ss->R[j].key=ss->R[j+1].key;
                ss->R[j+1].key=temp;
            }
        }
    }
    for(int i = 1;i<= ss->length;i++){printf("%d  ",ss->R[i].key);
    }
}

//二分查找法
int Search(SSTable *ss,int x){int low = 1,high,mid;
    high = ss->length;
    while (low<= high){mid = (low + high) / 2;
        if (ss->R[mid].key == x){return mid;
        }
        else if (ss->R[mid].key< x){low = mid;
        }
        else if(ss->R[mid].key >x){high = mid;
        }
    }
}

int main() {SSTable ss;
    int x,location;
    Create_List(&ss);
    Bubble(&ss,ss.length);
    while (1){printf("\n请输入需要查找的元素：");
        scanf("%d",&x);
        Search(&ss,x);
        location = Search(&ss,x);
        if (location == 0){printf("查找失败！\n");
        } else{printf("数据在查找表中的位置为：%d\n",location);
        }
    }
    return 0;
}

在主函数也给一个while的死循环，方便多次查找，不用查找一次运行一次代码。

这个代码出现一个bug，就是会在查找时候出现卡住，出不了结果的情况

希望有大佬帮帮忙看看什么情况 嘻嘻~
如果有错，望指出更正。向大家学习！

最后：这是我一次数据结构作业。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧