python实现二分查找算法

时间:2021-05-22

二分查找算法:简单的说,就是将一个数组先排序好,比如按照从小到大的顺序排列好,当给定一个数据,比如target,查找target在数组中的位置时,可以先找到数组中间的数array[middle]和target进行比较,当它比target小时,那么target一定是在数组的右边,反之,则target在数组的左边,比如它比target小,则下次就可以只比较[middle+1, end]的数,继续使用二分法,将它一分为二,直到找到target这个数返回或者数组全部遍历完成(target不在数组中)

优点:效率高,时间复杂度为O(logN);
缺点:数据要是有序的,顺序存储。

python的代码实现如下:

#!/usr/bin/python env# -*- coding:utf-8 -*-def half_search(array,target): low = 0 high = len(array) - 1 while low < high: mid = (low + high)/2 if array[mid] > target: high = mid - 1 elif array[mid] < target: low = mid + 1 elif array[mid] == target: print 'I find it! It is in the position of:',mid return mid else: print "please contact the coder!" return -1if __name__ == "__main__": array = [1, 2, 2, 4, 4, 5]

运行结果如下:

I find it! It is in the position of: 44-1I find it! It is in the position of: 00-1

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章