当前位置：首页 > news >正文

C:每日一题：二分查找

news 来源：原创 2024/9/22 17:40:29

1、知识介绍：

1.1 概念：

二分查找是一种在有序数组中查找某一特定元素的搜索算法

1.2 基本思想：

每次将待查找的范围缩小一半，通过比较中间元素与目标元素的大小，来决定是在左半部分还是右半部分继续查找。

举个生活中的小例子：

比如说你朋友和你说她买了一件衣服价格不超过300元，然后让你猜一猜具体的价格，你肯定不会像 1 2 3……这样一个一个猜，而是先猜中间值150，如果实际价格比150大，则0~150之间的数字就不需要再猜，此时范围便缩小到150~300；这时候再猜225，如果实际价格小于225元，则225~300之间的数字就不需要再猜了，经过这样几次的猜测后，范围会逐渐缩小，大大提高了猜中数字的效率，这种思想就是二分查找。

1.3 二分查找的优缺点：

优点：二分查找的效率很高，在查找有序数组中的数字时，比遍历数组的效率高很多；

不足：二分查找的使用条件很苛刻，只有在有序数组中才能使用二分查找。

2、题目

写一个二分查找函数

功能：在一个升序数组中查找指定的数值，找到了就返回下标，找不到就返回-1.

int arr[ 10] = {11,23,23,56,77,88,98,111,121,131}

3、思路：

关于查找数组中的元素，我们一般是通过下标来锁定元素

3、分析main函数

int main()
{int arr[] = {11,23,23,56,77,88,98,111,121,131};int k = 0;scanf("%d", &k);//输入想要找的值int sz = sizeof(arr) / sizeof(arr[0]);//获取元素个数int left = 0;int right = sz - 1;int result = bin_search(arr, left, right, k);if (result != -1) {printf("找到了，下标为: %d\n", result);}else {printf("未找到\n");}return 0;
}

3.1 代码解释int left = 0; int right = sz - 1;

3.2 代码解释 int result = bin_search(arr, left, right, k);

bin_search是一个自定义函数，用来实现二分查找的过程

int result = bin_search(arr, left, right, k);是调用了一个名为 bin_search 的函数，并将返回值存储在变量 result 中。

arr 是要进行查找操作的数组。
left 和 right 分别是数组的起始下标和结束下标，确定了当前要查找的范围。
k 是要在数组中查找的目标值。

4、分析函数bin_search

int bin_search(int arr[], int left, int right, int k)
{int mid = (left + right) / 2;while (left <= right){int mid = (left + right) / 2;if (arr[mid] < k){left = mid + 1;}else if (arr[mid] > k){right = mid - 1;}else{return mid;}}return -1;
}

4.1 二分查找的运算方式：

5、完整代码

#include <stdio.h>
int bin_search(int arr[], int left, int right, int k)
{int mid = (left + right) / 2;while (left <= right){int mid = (left + right) / 2;if (arr[mid] < k){left = mid + 1;}else if (arr[mid] > k){right = mid - 1;}else{return mid;}}return -1;
}int main()
{int arr[] = {11,23,23,56,77,88,98,111,121,131};int k = 0;scanf("%d", &k);int sz = sizeof(arr) / sizeof(arr[0]);int left = 0;int right = sz - 1;int result = bin_search(arr, left, right, k);if (result != -1) {printf("找到了，下标为: %d\n", result);}else {printf("未找到\n");}return 0;
}

函数bin_search 会在给定的数组范围 left 到 right 内查找目标值 k ，并返回找到目标值时的下标或者 -1 表示未找到。然后这个返回值就被赋值给了 result ，后续的代码会根据 result 的值来判断是否找到了目标值。

6、不使用函数的二分查找

#include <stdio.h>
int main()
{int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };int k = 7;scanf("%d", &k);int sz = sizeof(arr) / sizeof(arr[0]);int left = 0;int right = sz - 1;int flag = 0;while(left <= right){int mid = (left + right) / 2;if (arr[mid] < k){left = mid + 1;}else if (arr[mid] > k){right = mid - 1;}else{printf("找到了,下标位%d\n", mid);flag = 1;break;}}if (flag == 0)printf("没找到");return 0;
}

如果觉得还不错的话，就给小编一个三连吧！！！