二分查找

何为二分查找

二分查找也称折半查找，它是一种效率较高的查找算法，如果查找的元素包含在列表中，二分查找返回其位置。

基本思想

假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

代码实现

下面是C语言代码

#include <stdio.h> //用二分法查找数字number在有序升数组array中的位置，该数组长度为len //返回值>=0时是位置下标，=-1时是查找失败 int binarySearch(int number, int array[], int len){ int res = -1; int left = 0; int right = len - 1; int mid = (left + right) / 2; while (left <= right){ if (number < array[mid]){ right = mid - 1; } else if (number>array[mid]){ left = mid + 1; } else if (number==array[mid]){ res = mid; break; } mid = (left + right) / 2; } return res; } int main(){ int a[10] = { 14, 16, 17, 48, 49, 67, 84, 91, 99, 105 }; printf("99所在的数组下标是%d\n", binarySearch(99, a, 10)); printf("48所在的数组下标是%d\n", binarySearch(48, a, 10)); printf("17所在的数组下标是%d\n", binarySearch(17, a, 10)); printf("21所在的数组下标是%d\n", binarySearch(21, a, 10)); return 0; }

下图是运行结果

时间复杂度

由于二分查找在查找的过程中不断的将所查找表的长度减半，很容易得出时间复杂度是log N。

这就是二分查找的内容了，祝大家学习愉快。