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

文章目录

• 1. 二分查找思想
• 2. 代码实现
• • 2.1 未封装函数
  • 2.2 封装函数（使用while循环）
  • 2.3 封装���数（使用递归）

    1. 二分查找思想

    二分法：二分查找算法是一种在有序数组中查找某一特定元素的搜索算法，其思想就是不断地将有序查找表“一分为二”，逐渐缩小搜索区域，进而找到目标元素。

    • 搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜 素过程结束；
    • 如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
    • 如果在某一步骤数组 为空，则代表找不到。
    • 这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半，时间复杂度为Ο(logn) 。

      注：使用二分查找的前提条件是，数组已经是有序的

      二分查找图解：以有序数组 {10, 14, 19, 26, 27, 31, 33, 35, 42, 44} 为例，查找元素

      初始状态：

      第一轮查找：根据 2733，可以判定 33 位于 35 左侧的区域，更新搜索区域。

      第三轮查找：31 int a[N] = {1, 5, 8, 11, 19, 22, 31, 35, 40, 49, 50}; // 准备好一个已经排序好的数组 int low = 0, high = N - 1, mid, target; printf("请输入要查找的值："); scanf("%d", &target); printf("%d\n", target); // 当左边界还未超过右边界时，进行二分查找 while(low mid = (low + high) / 2; // 每次循环重新给mid赋值，改变中间值的下标 printf("low = %d, high = %d, mid = %d\n", low, high, mid); // 此处打印各个下标值，方便观测下标变化 // 如果中间值等于目标值，说明查找成功，此时跳出循环 if(a[mid] == target){ printf("目标值的下标是%d\n", mid); break; } // 如果中间值大于目标值，说明目标值在左半边，此时改变右边界的下标（缩减右半边） if(a[mid] target) high = mid - 1; // 如果中间值小于目标值，说明目标值在右半边，此时改变左边界的下标（缩减左半边） if(a[mid]