二分查找【多种方法+图解】

二分查找【多种方法+图解】

• 前言
• 介绍以及简单思路介绍
• 第一种解法，[left,right]区间
• 第二种解法，[left,right)区间
• 递归解���

  前言

  二分查找其实是一个十分容易理解的方法，在很多人思路里都知道先这个…再那个…，其实二分查找也有许多细节需要去细细分析

  介绍以及简单思路介绍

  二分查找是对于一个有序数组进行查找，如果数组无序，可以通过最简单的冒泡排序去排序

  • 1找到数组的中间位置
  • 检查中间位置的数组是否与要查找的数据key相等
    • a: 相等，就找到，打印下标跳出循环
    • b: key，则key可能在arr[mid]的左半侧，继续到左半侧进行二分查找
    • c: key》arr[mid]，则key可能在arr[mid]的右半侧，继续到右半侧进行二分查找
    • 如果找到，打印下标，否则继续，直到区间中没有元素时，说明key不在集合中

      可见这里的中间值是一个十分重要的值，对于求这个中间的值还有一个小细节：

      left为数组左下标，right为数组右下标

      提到求中间值，我们第一时刻就会想到：int mid = (left+right)/2,这样在一般情况下是没有问题的

      但是int类型是有它的范围的，有可能两个int类型的值相加的值就会超过int的最大范围值，也就是溢出

      所以这里我们最好这样写：int mid = left + (right - left) / 2,这样就会避免溢出，其实把这个式子进行通分，就会得出(left+right)/2这个式子，他们的本质实际是一样的，只是后者避免溢出而已

      ---

      接下来有两种解法，我们要注意三点：

      1. right的右半侧区间取值，决定了后续的写法
      2. while循环条件是否有等号
      3. 更改right和left的边界时，是否要+1和-1

      第一种解法，[left,right]区间

      int main()
      {
      	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
      	int key = 0;
      	scanf("%d" ,&key);
      	int left = 0;
      	int right = sizeof(arr) / sizeof(arr[1]) - 1;
      	
      	while (left 
      		int mid = left + (right - left) / 2;
      		if (arr[mid]  key)
      		{
      			right = mid - 1;
      		}
      		else if (arr[mid]  right)
      	{
      		printf("找不到\n");
      	}
      	return 0;
      }
      

      在while的循环条件是left int arr[] = { 1,2,3,4,5,6,7,8,9,10 }; int key = 0; scanf("%d", &key); int left = 0; int right = sizeof(arr) / sizeof(arr[1]); while (left = right) { printf("找不到\n"); } return 0; }

      要注意的是：这里的right的初始值为sizeof(arr) / sizeof(arr[1])为数组的长度，实际上是数组最后一个的下标的下一位

      这里的while中的判断语句是left key 就right =mid这里与上一解法不同

      递归解法

      void find(int* arr, int n, int left, int right)
      {
      	if (left 
      		int mid = left+(right-left)/2;
      		if (n == arr[mid])
      		{
      			printf("找到了%d它在下标%d处",n,mid);
      		}
      		else if (n  arr[mid])
      		{
      			find(arr, n, mid + 1, right);
      		}
      		else
      		{
      			find(arr, n, left, mid - 1);
      		}
      	}
      	if (left > right)
      	{
      		printf( "没找到");
      	}
      }
      int main()
      {
      	int arr[10] = { 5,8,10,26,74,100,102,120,136,180};
      	int len = sizeof(arr) / sizeof(arr[0]);
      	int n1 = 0;
      	int left = 0;
      	int right = len - 1;
       	printf("输入你想要查找的数\n");
      	scanf("%d",&n1);
      	find(arr, n1, left, right);
      	return 0;
      }
      

      这里原理和解法一相同，这里不多介绍