学习数据结构与算法，二分查找法是必须要掌握的算法，该算法前提是待查找序列已单调有序，从序列中间值开始与目标值匹配，如果相等，则查找成功，如果比目标值大，则在待查找序列前半段继续查找，如果比目标值小，则在待查找序列后半段继续查找，直到查找成功，或待查找序列没有与目标值相匹配的值。 二分查找法时间复杂度为O（logn），而顺序查找时间复杂度为O（n） 输入：先输入一个整数n，为待查找学生个数。接着输入n个学生信息，学生信息包括学号，姓名，性别，年龄。接着再输入一个学号，为想要查找的学生学号 输出：目标学生的全部信息 示例：4 01 杨凯 男 19 02 周峰 男 20 03 张莹 女 20 04 刘宇 男 19 03 03 张莹 女 20 代码：
#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<string.h>#include<algorithm>using namespace std;struct Student{ //学生结构体 char id[100];//学号 char name[100];//姓名 int age;//年龄 char sex[5];//性别 bool Operator<(const Student & A)const { //重载“<”运算符，下面的sort函数要用到 return strcmp (id, A.id) < 0; }}stu[1000];int main (){ int n; scanf ("%d", &n); for (int i = 0; i < n; i++) { scanf ("%s%s%s%d", stu[i].id, stu[i].name, stu[i].sex, &stu[i].age); } sort (stu, stu + n); //按照学号由大到小排列 while (1) { int ans = -1; char x[30]; scanf ("%s", x); int high = n - 1, low = 0; //初始最高下标为n-1，最低下标为0 while (high >= low) { //二分查找核心代码，注意二分查找要求查找空间单调有序 int mid = (high + low) / 2; //取中间下标 int tmp = strcmp (stu[mid].id, x); //比较中间下标对应的学生学号与所要查找的学号是否相等 if (tmp == 0) { //相等，查找成功 ans = mid; break; } else if (tmp > 0) //若stu[mid]大于x，则让最高下标成为中间下标-1，重新查找 high = mid - 1; else // low = mid + 1; //若stu[mid]小于x，则让最低下标成为中间下标+1，重新查找 } if (ans == -1) { //查找失败 PRintf ("No Answer!/n"); } else printf ("%s %s %s %d/n", stu[ans].id, stu[ans].name, stu[ans].sex, stu[ans].age); } system ("pause"); return 0;}新闻热点
疑难解答
