【21天算法学习】折半查找

作者简介：

🍀姓姜，字君竹。

🍁浅薄观点：科以载文，文以载道

🌱软件技术升计科，计划考研

🌾要有最朴素的生活和最遥远的梦想，即使明日，天寒地冻，路遥马亡

概念及介绍

1.  折半查找（搜索），也称二分查找（搜索）、对数搜索，是一种在有序数组中查找某一特定元素的搜索算法。

 搜索从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索结束。如果要查找的元素大于或者小于之中间元素，则在数组大于或小于中间元素的那一半中查找，且也是从这一半的中间元素开始比较。然后一直重复上述流程，直到找的要找的元素，或者找完不能再折半查找为止。这种搜索算法每一次比较都使得搜索范围缩小了一半。

 折半查找查找速度快、次数少、平均性能好，但查找对象必须是有序的，且很难实现插入删除。所以折半查找使用不常变动且需要频繁查找的有序列表。

2.时间空间复杂度

 时间复杂度与寻找次数相关，如果要寻找的值第一次就找到了，则此时的时间复杂度为常数级O(1)。折半查找每查找一次，搜索空间就会折半，所以折半查找正常的时间复杂度是一个以2位底，相对于n的对数O(log2n)。

 折半算法并没有改变原有的元素集合，只需要几个变量记录相关信息，所以空间复杂度为常量级O(1)。

3.图解

1. 代码实现
   

int main() {
  int a[] = { 0, 12, 23, 24, 25, 34, 45, 56, 67, 68, 78, 89, 90 };
  int key = 24;
  int left = 0;
  int right = sizeof(a) / sizeof(a[0]) - 1;
  while (left <= right) {
    int mid = (left + right) / 2;
    if (a[mid] == key) {
      printf("下标是%d", mid);
      return 0;
    }
    else if (a[mid] < key)
      left = mid + 1;
    else if (a[mid] > mid)
      right = mid - 1;
  }
  if (left > right) {
    printf("没找到");
  }
  return 0;
}

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。