初识 二分查找

初识 二分查找

一些常见的大O运行时间（以排序算法举例）

O(log n), 也叫对数时间，这样的算法包括二分查找

O(n) , 也叫线性时间，这样的算法包括简单查找

O(n*log n),快速排序——一种较快的排序算法

O(n^2), 选择排序——一种较慢的排序算法

O(n!), 旅行商问题解决方案—一种非常慢的算法

二分查找测试

/*二分查找测试*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define NUM 5
int binary(int* list, int item);
int main() {int find,find1;int num[NUM] = { 1,3,5,7,9 };find = binary(num, 3);find1 = binary(num, -1);printf("%d\n%d", find, find1);
}
int binary(int *list,int item){int mid;int guess;int low = 0;int high = NUM- 1;while (low <= high){mid = (low + high) / 2;guess = list[mid];if (guess == item)return list[mid];if (guess > item)high = mid - 1;if (guess < item)low = mid + 1;}return NULL;}

用二分查找在有序列表中查找人名

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define NUM 5
int binary(const char* list[], const char* item);
int main() {int find_qsort,find1_qsort;const char* list[10] = {"Amelia","Ava","Charlotte","Emma","Mia","Isabella","Olivia","Sophia","Zala"};find_qsort = binary(list, "Ava");find1_qsort = binary(list, "Mia");printf("%s\n%s", list[find_qsort], list[find1_qsort]);
}
int binary(const char *list[],const char *item){int mid;const char* guess;int low = 0;int high = NUM- 1;while (low <= high){mid = (low + high) / 2;guess = list[mid];if (guess == item)return mid;if (guess > item)high = mid - 1;if (guess < item)low = mid + 1;}return NULL;}