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

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

• 前言
• 介绍以及简单思路介绍
• 第一种解法，[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;}

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