【C语言】二分查找（详解）

🎥 岁月失语唯石能言的个人主页        

🔥个人栏专：秒懂C语言

⭐若在许我少年时，一两黄金一两风    

目录

一、二分查找的思路 

二、思路分析

2.1定义变量

2.2逻辑分析

三、代码实现

总结

一、二分查找的思路 

       二分查找是一种高效的查找算法，尤其适用于有序数组。它的基本思想是通过将查找区间逐步缩小一半，从而快速定位目标元素。对于大型数据集，二分查找的效率远高于线性查找。然而，它要求数据必须有序，且实现相对复杂一些。总的来说，二分查找是一种非常实用和强大的工具，在许多场景下都能发挥出其独特的优势。

   举个例子：

        朋友让你猜他刚买的一件衣服的价格，告诉你在（0~100）元之间。

        我们一般都是先猜中间价位50元，他说猜低了，你再猜75元，这样一步步的缩减范围。直到锁定86元。你只要用几次二分查找就能找到价格。而你要是从一开始猜你得猜86次，速度和效率提升非常大。

二、思路分析

例子:        int arr[] = {1,2,3,4,5,6,7,8,9,10};

首先题目会给你一个有序数组，让你找出某个数字比如说7的下标.

2.1定义变量

• 首先我们定义lift，right,key,mid四个变量。left的下标为0；right的下标用sizeof（arr）/sizeof（arr[0]）-1   （整个数组的大小）/（一个数组元素的大小）-1   因为数组的下标是从0开始所以要减1。
• mid = (left + right) / 2; 如果left和right比较大的时候可能会越界，这时候可以改良一下：
• mid = left+(right-left)/2;

  

  2.2逻辑分析

  • 然后我们需要拿arr[mid]（50元）与key去比较大小然后不断缩小范围。
  • 如果arr[mid] == key，那就说明找到了，直接打印。
  • 如果arr[mid] > key说明你猜大了那你就要缩小范围1~100就要改成1~49（因为50比价格贵不需要取50元）所以right下标就要改成mid-1
  • 同理，如果arr[mid]
  • 当然有人会担心mid = (left + right) / 2中(left + right)是奇数除出来不是整数怎么办。/ 符号位会自动舍掉余数不用当心。

    if (arr[mid] == key)
    {
    	printf("找到了,下标是%d\n", mid);
    	break;
    }
    if (arr[mid] > key)
    {
    	right = mid - 1;
    }
    if (arr[mid]  
    

    • 然后在使用while循环来实现不断猜数字的过程
    • while的条件就设置成left right) printf("找不到\n"); return 0;

      同理，如果是降序数组的话只需要把 right = mid - 1;和 left = mid + 1;交换位置就行：

      

      ---

      三、代码实现

      这是升序的代码：

      #include 
      int main()
      {
      	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
      	int left = 0;
      	int right = sizeof(arr) / sizeof(arr[0]) - 1;
      	int key = 7;//要找的数字
      	int mid = 0;//记录中间元素的下标
      	while (left  key)
      		{
      			right = mid - 1;
      		}
      		if (arr[mid]  right)
      		printf("找不到\n");
      	return 0;
      }

      这是降序代码：

      #include 
      int main()
      {
      	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
      	int left = 0;
      	int right = sizeof(arr) / sizeof(arr[0]) - 1;
      	int key = 7;//要找的数字
      	int mid = 0;//记录中间元素的下标
      	while (left  key)
      		{
      			left = mid + 1;
      		}
      		if (arr[mid]  right)
      		printf("找不到\n");
      	return 0;
      }

      往期文章推荐：

      C语言如何生成随机数以及设置随机数的范围。（超详细）：http://t.csdnimg.cn/62LIP

      【C语言】函数调用及创建，并将数组传参到函数：http://t.csdnimg.cn/cU9Ku

      【C语言】——函数递归，用递归简化并实现复杂问题：http://t.csdnimg.cn/nsS4d

      ---

      总结

      以上就是关于二分查找的相关知识，二分查找虽然性能比较优秀，但应用场景也比较有限，底层必须依赖数组，并且还要求数据是有序的。所以我们在选用算法时需要从多方面考虑。