目录
一.什么是二分查找法?
二.算法要求
三.算法思想
图解(要找的数k的值为3)
参考代码
一.什么是二分查找法?
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序储存结构,而且表中元素按关键字有序排列。
二.算法要求
1.必须是有序排列。
三.算法思想
例如数列 arr[]={1,2,3,4,5,6,7,8,9} 查找的数为k=3;
这里的left,right,mid记录的是数组下标
1.用left指向数列最左边的数(1),即left=0;
2.用right指向数列中最右边的数(9),即right=8;
3.用mid记录下标为(left+right)/2的数,即数组中间的数(5);
这一步完成后,就是把arr[]数组分为了两个子数组,用arr[mid]隔开
即: {1,2,3,4} 5 {6,7,8,9}
4.用arr[mid]与目标数k的大小进行比较,有三种情况
(1)arr[mid]=k; 即找到了
(2)如果k比arr[mid](即中间的那个数)大,则说明目标数(k)在右边的那个子数组中,所以就变成了在右边数组中找目标元素;方法和上面的类似,所以我们只需要将left指向改变为右边那个子数组的最左边的元素,即left=mid+1;
(3)同理,如果k比arr[mid]小,则说明目标数(k)在左边的那个子数组中,所以就变成了在左边数组中找目标元素;我们只需要将right指向改变为左边那个子数组的最右边的元素,即right=mid-1;
5.只需要重复第四步的操作就可以把k的值的位置找到;
图解(要找的数k的值为3)
参考代码
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
int main()
{
int arr[] = { 1,2,3,4,5,6,7,8,9,10};
int k = 0;
scanf("%d",&k);
int left = 0;
int right = sizeof(arr) / sizeof(arr[0]) - 1;
while (left < right)
{
int mid = (left + right)/2;
if (arr[mid] == k)
{
printf("找到了,下标为%d\n",mid);
break;
}
else if (arr[mid] < k)
{
left = mid + 1;
}
else
{
right = mid-1;
}
}
if (left > right)
{
printf("没找到,数不在该数列上\n");
}
return 0;
}
输出
文章来源:https://www.toymoban.com/news/detail-499367.html
!!!!文章来源地址https://www.toymoban.com/news/detail-499367.html
到了这里,关于【二分查找】详细图解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!