二分查找的基本思想: 将 n 个元素分成大致相等的两部分,取 a[n/2] 与 x(查找目标值) 做比较,如果
x == a[n/2]
,则找到 x,算法中止;否则,如果x < a[n/2]
,则只要在数组 a 的左半部分继续搜索 x,如果x > a[n/2]
, 则只要在数组 a 的右半部搜索 x。
使用二分查找算法的前提:待查找序列是有序的
由算法核心思想可知:每次对比都将下一步的比对范围缩小一半。每次比对后剩余数据项如下表:
即要找的元素正好在初始查找序列的中间一次比较出结果,时间复杂度为 O(1) 。
即比对范围只剩下 1 个数据项的情况这个数据项即为正要找的元素。这时,可求解如下方程组( i 为比较次数):
时间复杂度为 O(log(n))
进行平均时间复杂度分析时需要讨论:随着元素个数n的增多,需要几步算法才能终止?查找成功有多少种情况?查找失败有多少种情况?
为比较次数。易知,对于
, 会有
:
根据初等数学等差乘等比数列求和的错位相减法/裂项相消法。易知,
。
综上可得,
非常大时,可得
所以
# -*- coding: utf-8 -*-
# binary_search
def binary_search(list_1, item):
low = 0
high = len(list_1)-1
while low <= high:
'''使用 // 整除运算符可以不用int进行类型转换'''
#每次都检查中间的元素
mid = (low + high)/2
guess = list_1[int(mid)]
if guess == item:
return int(mid)#返回所在位置的索引
if guess < item: #猜的数字小了,修改low
low = mid+1
if guess > item: #猜的数字大了,修改high
high = mid-1
return None
def main():
list_2 = [1,2,3,4,5,6,7,8,9]
print(binary_search(list_2, 8))
print(binary_search(list_2, 10))
main()
#include<iostream>
#include<typeinfo>
using namespace std;
int binary_search(int a[9],int n,int x)//n为元素个数
{
int mid;
int high,low=0;
int guess;
high = n-1;//数组下标从0开始
while(low <= high)
{
mid = (high+low)/2;
guess = a[mid];
if(guess == x)
return mid;
if(guess > x)
high = mid-1;
if(guess < x)
low = mid+1;
}
return -1;
}
int main()
{
int temp;
int a[9] = {1,2,3,4,5,6,7,8,9};
cout<<sizeof(a)/sizeof(int)<<endl;
cout<<typeid(sizeof(a)/sizeof(int)).name()<<endl;
temp = binary_search(a,sizeof(a)/sizeof(int),5);
cout<<temp<<endl;
return 0;
}
附:C++ 使用头文件typeinfo下的typeid(parameter).name()可获取参数获取类型名