【C语言必刷题】3.二分查找

爱敲代码的小杨.

发布于 2024-05-07 19:15:56

870

发布于 2024-05-07 19:15:56

文章被收录于专栏：JavaJava

?前言

二分查找又称为折半查找，是分治算法基础上设计出来的查找算法。二分查找算法仅适用于有序序列，它只能用升序序列或者降序序列中查找目标元素。

?算法描述

二分查找的核心思想：不断地缩小搜索的区域，降低查找目标元素的难度。

前提：有已排序的数组arr。
定义左边界（Left），定义右边界（Right），确定搜索范围，循环执行二分查找.
获得中间下标 Middle = (Left + Right) / 2。
中间下标的值，arr[Middle] 与待搜索的值 t 进行比较。
- arr[Middle] == t 表示知道了，返回中间下标
- arr[Middle] > t 中间值右侧的其他元素都大于t，不需要比较，中间下标左边去找，Middle - 1 设置右边界，重新查找。
- arr[Middle] < t 中间值左侧的其他元素都小于t，不需要比较，中间下标右边去找，Middle + 1 设置左边界，重新查找。
当 Left > Right ,表示没有找到，循环结束。

?算法实现

void binarysearch(int arr[], int Length, int t) // 数组、数组长度和要查找的数
{
	int find = -1;//标记

	int Left = 0; // 左边界
	int Right = Length - 1; // 右边界
	int Middle = 0; // 中间值

	while (Left <= Right) // Left > Right ,表示没有找到，循环结束。 
	{
		Middle = (Left + Right) / 2;
		if (arr[Middle] == t) // 找到了
		{
			find = 1;
			break;
		}
		else if (arr[Middle] > t) // 右侧都大于t
			Right = Middle - 1;
		else // 左侧都小于t
			Left = Middle + 1;
	}

	if (1 == find)
		printf("找到了，下标为：%d\n", Middle);
	else
		printf("没有找到\n");
}

?测试代码

int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	int Length = sizeof(arr) / sizeof(arr[0]); // 计算数组长度
	int t = 0;
	scanf("%d", &t);

	binarysearch(arr, Length, t);

	return 0;
}

?解决溢出问题

当Left 和 Right 都较大时，Left + Right 有可能会超出整数的范围，造成计算错误，可以使用以下解决方法。

Middle = Left + (Right - Left) / 2;

?代码

#include<stdio.h>

void binarysearch(int arr[], int Length, int t);

int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	int Length = sizeof(arr) / sizeof(arr[0]); // 计算数组长度
	int t = 0;
	scanf("%d", &t);

	binarysearch(arr, Length, t);

	return 0;
}	

void binarysearch(int arr[], int Length, int t) // 数组、数组长度和要查找的数
{
	int find = -1;//标记

	int Left = 0; // 左边界
	int Right = Length - 1; // 右边界
	int Middle = 0; // 中间值

	while (Left <= Right) // Left > Right ,表示没有找到，循环结束。 
	{
		Middle = Left + (Right - Left) / 2;
		if (arr[Middle] == t) // 找到了
		{
			find = 1;
			break;
		}
		else if (arr[Middle] > t) // 右侧都大于t
			Right = Middle - 1;
		else // 左侧都小于t
			Left = Middle + 1;
	}

	if (1 == find)
		printf("找到了，下标为：%d\n", Middle);
	else
		printf("没有找到\n");
}

本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-05-07，如有侵权请联系 cloudcommunity@tencent.com 删除

搜索