欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分法查找整型有序数组中具体的某个数

程序员文章站 2022-03-13 18:20:53
...

二分法

在数组中寻找某个元素时,一般都是从头到尾进行遍历。

为了提高效率,可以采用二分法,每次和中间的值做对比,缩小查找区间

 

解决思路

定义四个变量:left所查找区间的左边 right所查找区间的右边 mid所查找区间的中间值 和我们想要查找的数toFind

数学中我们可以这样表示:[left,right]     mid=(left+right)/2

如果toFind<mid ,那么所查找的区间更新为[left,mid)

如果toFind>mid,那么所查找的区间更新为(mid,right]

直到toFind=mid,就找到了我们想要查找的数字

代码示例

这里自己定义了一个数组{ 1, 5, 7, 13, 24, 16 },如果需要键盘输入自行修改即可

#include<stdio.h>
#include<windows.h>
#pragma warning(disable:4996)

int main()
{
	int toFind = 0;
	int arr[] = { 1, 5, 7, 13, 24, 16 };
	int left = 0;
	printf("请输入要查找的数字:\n");
	scanf("%d",&toFind);
	int right = sizeof(arr) / sizeof(arr[0]) - 1;
	while(left<=right){
		int mid = (left + right) / 2;
		if (toFind <arr[mid]){
			right = mid - 1;
		}
		else if (toFind>arr[mid]){
			left = mid + 1;
		}
        else{
			printf("找到了,数组下标为:%d\n", mid);
			break;
	    }		
	}
	if (left > right){
		printf("找不到!\n");
	}
	system("pause");
	return 0;
}

运行结果

二分法查找整型有序数组中具体的某个数

 

再吃一颗苹果~~加油鸭~~~

相关标签: c语言