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

本文主要是介绍【C语言必刷题】3.二分查找，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

📚博客主页：爱敲代码的小杨.

✨专栏：《Java SE语法》 | 《数据结构与算法》 | 《C生万物》

❤️感谢大家点赞👍🏻收藏⭐评论✍🏻，您的三连就是我持续更新的动力❤️

🙏小杨水平有限，欢迎各位大佬指点，相互学习进步！

🔥前言

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

🔥算法描述

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

1. 前提：有已排序的数组arr。
2. 定义左边界（Left），定义右边界（Right），确定搜索范围，循环执行二分查找.
3. 获得中间下标 Middle = (Left + Right) / 2。
4. 中间下标的值，arr[Middle] 与待搜索的值 t 进行比较。
   • arr[Middle] == t 表示知道了，返回中间下标
   • arr[Middle] > t 中间值右侧的其他元素都大于t，不需要比较，中间下标左边去找，Middle - 1 设置右边界，重新查找。
   • arr[Middle] < t 中间值左侧的其他元素都小于t，不需要比较，中间下标右边去找，Middle + 1 设置左边界，重新查找。
5. 当 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) // 右侧都大于tRight = Middle - 1;else // 左侧都小于tLeft = Middle + 1;}if (1 == find)printf("找到了，下标为：%d\n", Middle);elseprintf("没有找到\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) // 右侧都大于tRight = Middle - 1;else // 左侧都小于tLeft = Middle + 1;}if (1 == find)printf("找到了，下标为：%d\n", Middle);elseprintf("没有找到\n");
}

这篇关于【C语言必刷题】3.二分查找的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---