转贴:数据结构：二分查找

1．二分查找又称为折半查找，它要求要查找的顺序表必须是有序表，即表中结点按关键
字有序，而且要用顺序存储结构。
　　基本思想是：首先将给定值key与表中中间位置记录的关键字相比较，若两者相等，则
查找成功，不然根据比较的结果肯定下次查找的范围是在中间记录的前半部分仍是后半部
分，而后在新的查找范围内进行一样的查找，如此重复下去，直到在表中找到关键字与给定
值相等的记录，或者肯定表中没有这样的记录。
　　编写程序构造一个有序表La，从键盘接收一个关键字key，用二分查找法在La 中查找
key，若找到则提示查找成功并输出key所在的位置，不然提示没有找到信息。函数

//二分查找 #include <stdio.h> #include <stdlib.h> typedef int Status; typedef int KeyType; typedef int ElemType; typedef struct { ElemType *elem; int length; } SSTable; int Search_Bin ( SSTable ST, KeyType key ) { // 在有序表ST中折半查找其关键字等于key的数据元素。 // 若找到，则函数值为该元素在表中的位置，不然为0。 int low, high, mid; low = 1; high = ST.length; while (low <= high) { mid = (low + high) / 2; if (key == ST.elem[mid]) return mid; // 找到待查元素 else if (key < ST.elem[mid]) high = mid - 1; else low = mid + 1; } return 0; } int main() { SSTable ST; ST.elem = (ElemType *)malloc(100 * sizeof(ElemType)); int i = 0; for (i = 0;i < 100;i++) ST.elem[i] = i * 2; ST.length = 100; KeyType key; printf("请输入一个key进行查找："); scanf("%d", &key); getchar(); i = Search_Bin(ST, key); if (i) printf("位置：%d", i); else printf("没找到!"); getchar(); } code