二分查找的前提:
一个整形有序数组中查找具体某个数
以下以数组元素为偶数个做例
二分查找(折半查找)的思想:对于已按关键字排序的序列,经过一次比较,可将序列分割成两部分,然后只在有可能包含待查元素的一部分中继续查找,并根据试探结果继续分割,逐步缩小查找范围,直至找到或找不到为止。
下图为程序在数组中寻找整数6的过程
进入循环之前,先定义数组的左右下标:左下标为0,右下标为数组元素个数减去1
while (left <= right),当作下标小于右下标时,进入循环
第一次循环:
if 和else if语句内均没有break 语句,所以循环继续
第二次循环:
第三次循环:
跳出循环后判断right的关系,这个if语句是在没有找到的情况下进入 文章来源:https://www.toymoban.com/news/detail-507041.html
代码如下:文章来源地址https://www.toymoban.com/news/detail-507041.html
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int main()
{
int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };//已知的整形有序数组
int x = 0;//x是要寻找的数
int left = 0;//左下标
int right = sizeof(arr) / sizeof(arr[0]) - 1;//数组右下标
scanf("%d", &x);
while (left <= right)
{
int mid = left+(right-left)/2;//找到最中间的数
if (x < arr[mid])
{
right = mid-1;
}
else if (x > arr[mid])
{
left = mid+1;
}
else
{
printf("找到了,下标是%d\n", mid);
break;
}
}
if (right < left)
{
printf("没找到");
}
return 0;
}
除了给定整形有序数组外,我们还可以自己输入一个有序数组和需要查找的数
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int main()
{
int arr[100];
int j = 0;//j为需要寻找的数
int i = 0;
int left = 0;
int right = 0;
while (1)
{
scanf("%d", &arr[i]);
i++;
if (getchar() == '\n')
{
break;//遇到回车则证明数组输入结束
}
}
scanf("%d", &j);
right = i - 1;//总共输入了i个元素,最大下标为i-1
while (left <= right)
{
int mid = left + (right - left) / 2;
if (j < arr[mid])
{
right = mid - 1;
}
else if (j > arr[mid])
{
left = mid + 1;
}
else
{
printf("找到了,下标为%d\n", mid);
break;
}
}
//左右下标发生交叉的情况,则证明没有找到
if (left > right)
{
printf("没找到\n");
}
return 0;
}
到了这里,关于二分查找(C语言实现)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!