阿里云网站备案拍照点,外贸网站索引页多,重庆新闻频道在线直播观看,网站建设金手指专业1、知识介绍#xff1a;
1.1 概念#xff1a;
二分查找是一种在有序数组中查找某一特定元素的搜索算法
1.2 基本思想#xff1a;
每次将待查找的范围缩小一半#xff0c;通过比较中间元素与目标元素的大小#xff0c;来决定是在左半部分还是右半部分继续查找。
举个生…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;
} 如果觉得还不错的话就给小编一个三连吧
