【C语言】经典算法之二分查找

1.算法思想😀

⭐二分查找:

又称为折半查找，二分查找，适合对已经排序好的数据集合进行查找，时间复杂度0 (log2n) ,效率高。假设有-升序的数据集合，先找出升序集合中最中间的元素，将数据集合划分为两个子集，将最中间的元素和关键字key进行比较，，如果等 于key则返回,如果大于关键字key,则在前一个数据集合中查找，否则在后-个子集中查找，直到找到为止，如果没找到则返回-1;

2.算法步骤😀

⭐（1）首先确定整个查找区间的中间位置mid=(left+high)/2;

      (2)  用待查关键字值与中间位置关键字值进行比较

若相等，则查找成功;

             若大于，则在后半个区域中继续进行折半查找。

             若小于，则在前半个区域中继续进行折半查找。

             查找成功，返回关键字所在数组下标，没找到返回-1;

图解

3.代码😀

⭐假设我们在数组int arr[] = {1，2，3，4，5，6，7，8，9，10}查找数值7

#include<stdio.h>
int main()
{
  int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
  int k = 7;
  int left = 0;   //左下标
  int right = sizeof(arr) / sizeof(arr[0]);     //右下标
  while (left <= right)
  {
    int mid = (left + right) / 2;   //中间元素的下标
    if (arr[mid] < k)
    {
      left = mid + 1;
    }
    else if (arr[mid] > k)
    {
      right = mid - 1;
    }
    else
    {
      printf("找到%d的下标了:%d", k, mid);
      break;
    }
  }
}