查找算法——二分查找

一、算法介绍

1.算法思想

二分查找也称折半查找，是一种效率比较高的查找算法，但是运用前提是查找的序列已经有序。其核心思想就是利用序列有序的特点，每次对序列中间元素进行比较，判断其与待查找元素的大小关系，来确定待查找元素是否是当前元素，或是在当前元素的左半部分还是右半部分，从而每次比较都能够淘汰一半的元素，缩小查找区间，所以其拥有较高的查找效率。

2.算法流程

示例：给定序列{1，2，3，4，5，6，7，8，9}，查找元素3。

每次比较后，若没有查找到待查找元素，都需要根据比较结果改变查找区间一侧边界，然后更新mid的位置，再进行下一次查找。

二、算法实现

1.代码实现

#include<iostream>
using namespace std;
//成功：返回下标  失败：返回-1
int BinarySearch(int* arr, int size, int key) {//二分查找  
  int left = 0;
  int right = size - 1;
  while (left <= right) {//注意等于时，也需要比较
  int mid = (left + right) / 2;
  if (arr[mid] < key) {
    left = mid + 1;
  }
  else if (arr[mid] > key) {
    right = mid - 1;
  }
  else {//查找成功
    return mid;
  }
  }
  return -1;//查找失败
}
void Test() {
  int arr[] = { 1,2,3,4,5,6,7,8,9 };
  int size = sizeof(arr) / sizeof(arr[0]);
  int key;
  cout << "请输入待查找元素：";
  cin >> key;
  int index = BinarySearch(arr, size, key);
  if (index == -1) {
  cout << endl << "没有待查找元素！" << endl;
  }
  else {
  cout << endl << "元素" << key << "所在位置下标为：" << index << endl;
  }
}
int main() {
  Test();
  return 0;
}

2.测试用例及结果

序列：1，2，3，4，5，6，7，8，9

查找元素3：

查找元素：9

查找元素：10

查找元素：0

三、性能分析

1.时间复杂度

最坏情况O( )：

根据算法思想可知，最坏情况即最后一次比较才找到待查找元素，也即是left与right重叠，查找区间内只剩一个元素时。根据算法思想每次淘汰一半元素可知，就相当于每次查找区间内元素减少一半，减少几次后只剩1个元素即最大的查找次数，即 次，所以最坏情况下的时间复杂度为O( )

最好情况O(1)：

最好情况即只需要比较一次就找到待查找元素，根据算法思想可知此时待查找元素刚好位于序列的中间位置，所以最好情况下的时间复杂度为O(1)。

平均情况O( )：

综合两种情况，二分查找的时间复杂度为O( )。

2.空间复杂度

O(1)

由于算法中只设置了几个临时变量用于限定查找区间和查找元素，并没有借助额外的辅助空间，所以空间复杂度为O(1)。