二分法查找python

⑴ 关于python里的二分法

因为他已经把middle位置上的数字已经检查过了，第一个if条件就是判断middle位置山的数字是不是想要的，既然这个条件不满足，那么就肯定不需要他，所以从他的上一位或下一位重新开始

⑵ python实现折半查找和归并排序算法

python实现折半查找和归并排序算法
今天依旧是学算法，前几天在搞bbs项目，界面也很丑，评论功能好像也有BUG。现在不搞了，得学下算法和数据结构，笔试过不了，连面试的机会都没有……
今天学了折半查找算法，折半查找是蛮简单的，但是归并排序我就挺懵比，看教材C语言写的归并排序看不懂，后来参考了别人的博客，终于搞懂了。
折半查找
先看下课本对于 折半查找的讲解。注意了，折半查找是对于有序序列而言的。每次折半，则查找区间大约缩小一半。low,high分别为查找区间的第一个下标与最后一个下标。出现low>high时，说明目标关键字在整个有序序列中不存在，查找失败。

看我用python编程实现:
defBinSearch(array, key, low, high): mid=int((low+high)/2) ifkey==array[mid]:# 若找到 returnarray[mid] iflow > high: returnFalse ifkey < array[mid]: returnBinSearch(array, key, low, mid-1)#递归 ifkey > array[mid]: returnBinSearch(array, key, mid+1, high) if__name__=="__main__": array=[4,13,27,38,49,49,55,65,76,97] ret=BinSearch(array,76,0,len(array)-1)# 通过折半查找，找到65 print(ret)
输出: 在列表中查找76.
76
时间复杂度：O(logn)
归并排序算法
先阐述一下排序思路：
首先归并排序使用了二分法，归根到底的思想还是分而治之。归并排序是指把无序的待排序序列分解成若干个有序子序列，并把有序子序列合并为整体有序序列的过程。长度为1的序列是有序的。因此当分解得到的子序列长度大于1时，应继续分解，直到长度为1.
(下图是分解过程，图自python编程实现归并排序)

合并的过程如下:

很好，你现在可以和别人说，老子会归并排序了。但是让你写代码出来，相信你是不会的……
来来来，看我用python写的归并排序算法:
defmerge_sort(array):# 递归分解 mid=int((len(array)+1)/2) iflen(array)==1:# 递归结束的条件，分解到列表只有一个数据时结束 returnarray list_left=merge_sort(array[:mid]) list_right=merge_sort(array[mid:]) print(">>>list_left:", list_left) print(">>>list_right:", list_right) returnmerge(list_left, list_right)# 进行归并 defmerge(list_left, list_right):# 进行归并 final=[] whilelist_leftandlist_right: iflist_left[0] <=list_right[0]:# 如果将"<="改为"<",则归并排序不稳定 final.append(list_left.pop(0)) else: final.append(list_right.pop(0)) returnfinal+list_left+list_right# 返回排序好的列表 if__name__=="__main__": array=[49,38,65,97,76] print(merge_sort(array))输出:
输出：
>>>list_left: [49]
>>>list_right: [38]
>>>list_left: [38, 49]
>>>list_right: [65]
>>>list_left: [97]
>>>list_right: [76]
>>>list_left: [38, 49, 65]
>>>list_right: [76, 97]
[38, 49, 65, 76, 97]
时间度杂度: 平均情况＝最好情况＝最坏情况＝O(nlogn)
空间复杂度:O(n)
稳定性:稳定
对序列{ 6, 5, 3, 1, 8, 7, 2, 4 }进行归并排序的实例如下:

使用归并排序为一列数字进行排序的宏观过程:

以上就是本文的全部内容，希望对大家的学习有所帮助

⑶ 谁会用python写个二分法查找的循环

#!/usr/bin/envpython
importsys

defsearch2(a,m):
low=0
high=len(a)-1
while(low<=high):
mid=(low+high)/2
midval=a[mid]

ifmidval<m:
low=mid+1
elifmidval>m:
high=mid-1
else:
printmid
returnmid
print-1
return-1

if__name__=="__main__":
a=[int(i)foriinlist(sys.argv[1])]
m=int(sys.argv[2])
search2(a,m)

⑷ 一个二分法搜索的python小程序，为什么按回车以后没有用

没写个py脚本里？你把函数调用也写在函数里了，所以，你的函数没有调用。注意缩进

⑸ 二分法的算法步骤是什么

在有序的有N个元素的数组中查找用户输进去的数据x。

算法如下：

1、确定查找范围front=0，end=N-1，计算中项mid=（front+end）/2。

2、若a[mid]=x或front>=end，则结束查找；否则，向下继续。

3.、若a[mid]<x，说明待查找的元素值只可能在比中项元素大的范围内，则把mid+1的值赋给front，并重新计算mid，转去执行步骤2；若a[mid]>x，说明待查找的元素值只可能在比中项元素小的范围内，则把mid-1的值赋给end，并重新计算mid，转去执行步骤2。

(5)二分法查找python扩展阅读

基本思想：假设数据是按升序排序的，对于给定值key，从序列的中间位置k开始比较，

如果当前位置arr[k]值等于key，则查找成功；

若key小于当前位置值arr[k]，则在数列的前半段中查找，arr[low，mid-1]；

若key大于当前位置值arr[k]，则在数列的后半段中继续查找arr[mid+1，high]，

直到找到为止，时间复杂度:O(log(n))。

⑹ 如何用二分法检索搜索开头字母 python

#!/usr/bin/envpython
#encoding:utf-8
defhalf_search(search_arr,search_str):
lb=0
ub=len(search_arr)-1
foriinrange(ub/2+1):
iflb>ub:
return-1
mid=(ub+lb)/2
ifsearch_arr[mid]==search_str:
returnmid
elifsearch_arr[mid]>search_str:
ub=mid-1
else:
lb=mid+1
if__name__=='__main__':
arr=[10,20,30,40,50,60,70]
printhalf_search(arr,1)
printhalf_search(arr,11)
printhalf_search(arr,22)
printhalf_search(arr,33)
printhalf_search(arr,40)
printhalf_search(arr,55)
printhalf_search(arr,66)
printhalf_search(arr,70)
printhalf_search(arr,8)

结果：

-1
-1
-1
-1
3
-1
-1
6
-1

⑺ python基础在线求解

(1) 10;5;10
(2)查找成功平均次数是10（有一半成功几率应该是5次，但算法估算是去常数的，所以用O表示还是10），不成功就是10
（3）二分是4次，不成功也是4次

a=[34,56,78,87,88,90,101,112,520,888]

defbinsearch(num):
start=0
end=len(a)-1
whilestart<=end:
mid=(start+end)//2
ifnum==a[mid]:
returnmid
elifnum>a[mid]:
start=mid+1
else:
end=mid-1
return-1

print(binsearch(8))

⑻ Python中的枚举法,随机法和二分法的优点是什么

摘要 枚举法的优缺点主要是：优点由于枚举法一般是现实生活中问题的“直译”，因此比较直观，易于理解；枚举法建立在考察大量状态、甚至是穷举所有状态的基础上，所以算法的正确性比较容易证明。