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

折半查找

程序员文章站 2024-03-20 18:59:16
...

折半查找的基本思想是,将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止。如 果x我们只要在数组a的左半部继续搜索x(这里假设数组元素呈升序排列)。如果x>a[n/2],则我们只要在数组a的右 半部继续搜索x。
写代码可以在整型有序数组中查找想要的数字,找到了返回下标,找不到返回 - 1.(折半查找)

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>
#include <stdlib.h>
int  Binary_search(int arr1[],int x,int y)
{
	int b = 0;
	printf("请输入你要查找的数:->");
	scanf("%d", &b);
	while (x <= y)
	{
		int mid = (x + y) / 2;
		if (arr1[mid] > b)
		{
			y = mid - 1;
		}
		else if (arr1[mid] < b)
		{
			x = mid+1;
		}
		else
		{
			return mid;
		}

	}
	if (x>y)
	{
		return -1;
	}
}
int main()
{
	int a = 0;
	int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	int left = 0;//最左边下标
	int right = sizeof(arr)/sizeof(arr[0])-1;//最右边下标
	a=Binary_search(arr,left,right);
	if (a!=-1)
	{
		printf("找到了,下标为%d\n", a);
	}
	if (a == -1)
	{
		printf("没找到\n");
	}
    system("pause");
    return 0;
}
相关标签: C语言