# c语言_Day12_07_11 ### 1、二分查找算法 也称折半查找，最坏情况查找log2n次 算法如下： 1. 找到中间元素索引[左右下标平均值] 2. 通过中间下标找到中间元素 3. 判断：若中间元素小于目标值则修改左下标(left = mid + 1)；若中间元素大于目标值则修改右下标(right = mid - 1)；若相等则直接返回 4. 循环：当左下标不大于右下标时继续查找，反之则未找到元素，应跳出循环 ```c int main() { // 查找数组 int arr[] = { 1,2,3,4,5,6,8,9 }; // 目标元素 int k = 3; // 数组长度 int length = sizeof(arr) / sizeof(arr[0]); // 定义左右下标 int left = 0; int right = length - 1; // 定义中间下标 int mid; // 当左下标仍不大于右下标时，查找仍在继续 while (left <= right) { // 计算中间下标 mid = (left + right) / 2; // 若中间下标元素小于目标值，则修改左下标 if (arr[mid] < k) { left = mid + 1; } // 若中间下标元素大于目标值，则修改右下标 else if (arr[mid] > k) { right = mid - 1; } // 若中间下标元素等于目标值，则直接返回 else { printf("已找到k，数组下标为%d\n", mid); break; } } // 当左下标仍大于右下标时，未找到元素 if (left > right) { printf("未找到k\n"); } return 0; } ``` ### 2、素数算法优化 基本算法：**试除法** ```c if (num > 1) { for (int i = 2; i < num; i++) { if (num % i == 0) { return 0; } } return 1; } else { return 0; } ``` 优化：上述算法需要从2遍历至num-1，实际上对于一个整数i，若i = a * b，则a和b中至少有1个数字小于等于i开平方 ```c int isPrime(int num) { if (num > 1) { // 1. 试除法 //for (int i = 2; i < num; i++) //{ // if (num % i == 0) // { // return 0; // } //} //2. 优化 for (int i = 2; i <= sqrt(num); i++) { if (num % i == 0) { return 0; } } return 1; } else { return 0; } } int main() { int count = 0; for (int i = 201; i <= 300; i+=2) // 偶数不可能为素数 { if (isPrime(i)) { printf("%d\n", i); count++; } } printf("count = %d\n", count); return 0; } ```