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

前言

介绍以及简单思路介绍

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

第二种解法，[left,right)区间

递归解法

前言

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

介绍以及简单思路介绍

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

1找到数组的中间位置

检查中间位置的数组是否与要查找的数据key相等

a: 相等，就找到，打印下标跳出循环

b: key<arr[mid]，则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这个式子，他们的本质实际是一样的，只是后者避免溢出而已

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

right的右半侧区间取值，决定了后续的写法

while循环条件是否有等号

更改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 <= right) //right位置有元素，要添加=号
  {
  int mid = left + (right - left) / 2;
  if (arr[mid] > key)
  {
    right = mid - 1;
  }
  else if (arr[mid] < key)
  {
    left = mid + 1;
  }
  else
  {
    printf("找到了，下标是：%d\n", mid);
    break;
  }
  }
  if (left > right)
  {
  printf("找不到\n");
  }
  return 0;
}

在while的循环条件是left <= right，就是哪怕left==right时，也会再循环一次

如果情况如下图时，也会再有一次循环去得到mid的值，如果判断条件是left<right时，则下图的情况则会退出循环，找不到要找的值

在改变left和right的边界时， 如果arr[mid] > key就·right = mid - 1若arr[mid] < key，就left = mid + 1这很容易理解，这也是人们通常最容易想出的一个二分查找

下面做一个例子

在{1,5,6,10,15,20,30,35}中，查找20

、

arr[mid]==key==20查找成功

第二种解法，[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]);
  while (left < right) 
  {
  int mid = left + (right - left) / 2;
  if (arr[mid] > key)
  {
    right = mid;
  }
  else if (arr[mid] < key)
  {
    left = mid + 1;
  }
  else
  {
    printf("找到了，下标是：%d\n", mid);
    break;
  }
  }
  if (left >= right)
  {
  printf("找不到\n");
  }
  return 0;
}

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

这里的while中的判断语句是left < right，若arr[mid] < key，就left = mid + 1这里和上一个解法相同，arr[mid] > key 就right =mid这里与上一解法不同

递归解法

void find(int* arr, int n, int left, int right)
{
  if (left <= right)
  {
  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;
}

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