python實(shí)現(xiàn)二分查找算法
更新時間：2017年09月21日 10:38:36 作者：nfzhlk
這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)二分查找算法，具有一定的參考價值，感興趣的小伙伴們可以參考一下
二分查找算法：簡單的說，就是將一個數(shù)組先排序好，比如按照從小到大的順序排列好，當(dāng)給定一個數(shù)據(jù)，比如target，查找target在數(shù)組中的位置時，可以先找到數(shù)組中間的數(shù)array[middle]和target進(jìn)行比較，當(dāng)它比target小時，那么target一定是在數(shù)組的右邊，反之，則target在數(shù)組的左邊，比如它比target小，則下次就可以只比較[middle+1, end]的數(shù)，繼續(xù)使用二分法，將它一分為二，直到找到target這個數(shù)返回或者數(shù)組全部遍歷完成（target不在數(shù)組中）
優(yōu)點(diǎn)：效率高，時間復(fù)雜度為O(logN)；
缺點(diǎn)：數(shù)據(jù)要是有序的，順序存儲。
python的代碼實(shí)現(xiàn)如下：
#!/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 -1
if __name__ == "__main__":
array = [1, 2, 2, 4, 4, 5]
運(yùn)行結(jié)果如下：
I find it! It is in the position of: 4 4 -1 I find it! It is in the position of: 0 0 -1
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
本文主要介紹了使用python遍歷指定城市的一周氣溫的實(shí)現(xiàn)方法。具有很好的參考價值，下面跟著小編一起來看下吧2017-03-03
這篇文章主要介紹了在Python中處理字符串之ljust()方法的使用,是Python學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-05-05
用Flask實(shí)現(xiàn)token登錄校驗(yàn)的解決方案
網(wǎng)站、小程序、APP 是否已經(jīng)登錄所代表的狀態(tài),代表一個概念是登錄態(tài), 我們常用的登錄態(tài)驗(yàn)證方式有cookie,session,token,token提供了另外一種不需要緩存賬戶和密碼的登錄狀態(tài)驗(yàn)證方式,本文給大家介紹了用Flask實(shí)現(xiàn)token登錄校驗(yàn)的解決方案,需要的朋友可以參考下2024-03-03
Python生成可執(zhí)行文件之PyInstaller庫的使用方式
PyInstaller是一個十分有用的第三方庫,通過對源文件打包,Python程序可以在沒有安裝Python的環(huán)境中運(yùn)行,也可以作為一個獨(dú)立文件方便傳遞和管理,下面這篇文章主要給大家介紹了關(guān)于Python生成可執(zhí)行文件之PyInstaller庫的使用方式,需要的朋友可以參考下2022-04-04
pandas的drop_duplicates無法去重問題解決
在我們利用Pandas進(jìn)行數(shù)據(jù)清洗的時候,往往會用到drop_duplicates()進(jìn)行去重,本文主要介紹了pandas的drop_duplicates無法去重問題解決,具有一定的參考價值,感興趣的可以了解一下2024-03-03
Python實(shí)現(xiàn)批量檢測HTTP服務(wù)的狀態(tài)
本文給大家分享的是一個使用python實(shí)現(xiàn)的批量檢測web服務(wù)可用性的腳本代碼，主要功能有測試一組url的可用性（可以包括HTTP狀態(tài)、響應(yīng)時間等）并統(tǒng)計(jì)出現(xiàn)不可用情況的次數(shù)和頻率等。2016-10-10
Python實(shí)現(xiàn)對字符串的加密解密方法示例
這篇文章主要介紹了Python實(shí)現(xiàn)對字符串的加密解密方法,結(jié)合實(shí)例形式分析了Python使用PyCrypto模塊進(jìn)行DES加密解密的相關(guān)操作技巧,需要的朋友可以參考下2017-04-04
Python?是一種代表簡單思想的語言，其語法相對簡單，很容易上手。本文精心篩選了Python中的八大核心語句，快來看看你都掌握了幾個呢2023-02-02
下面小編就為大家分享一篇對pandas中apply函數(shù)的用法詳解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-04-04
python生成requirements.txt文件的推薦方法
Python項(xiàng)目中必須包含一個requirements.txt文件,用于記錄所有依賴包及其精確的版本號,以便新環(huán)境部署,下面這篇文章主要給大家介紹了關(guān)于python生成requirements.txt文件的相關(guān)資料,需要的朋友可以參考下2022-07-07