學習數據結構與算法，二分查找法是必須要掌握的算法，該算法前提是待查找序列已單調有序，從序列中間值開始與目標值匹配，如果相等，則查找成功，如果比目標值大，則在待查找序列前半段繼續查找，如果比目標值小，則在待查找序列后半段繼續查找，直到查找成功，或待查找序列沒有與目標值相匹配的值。 二分查找法時間復雜度為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;}新聞熱點
疑難解答
