python實現(xiàn)二分查找算法

更新時間：2017年09月21日 10:38:36 作者：nfzhlk

這篇文章主要為大家詳細介紹了python實現(xiàn)二分查找算法，具有一定的參考價值，感興趣的小伙伴們可以參考一下

二分查找算法：簡單的說，就是將一個數(shù)組先排序好，比如按照從小到大的順序排列好，當給定一個數(shù)據(jù)，比如target，查找target在數(shù)組中的位置時，可以先找到數(shù)組中間的數(shù)array[middle]和target進行比較，當它比target小時，那么target一定是在數(shù)組的右邊，反之，則target在數(shù)組的左邊，比如它比target小，則下次就可以只比較[middle+1, end]的數(shù)，繼續(xù)使用二分法，將它一分為二，直到找到target這個數(shù)返回或者數(shù)組全部遍歷完成（target不在數(shù)組中）

優(yōu)點：效率高，時間復雜度為O(logN)；
缺點：數(shù)據(jù)要是有序的，順序存儲。

python的代碼實現(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]

運行結果如下：

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)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章:

詳解Python如何實現(xiàn)Excel數(shù)據(jù)讀取和寫入
這篇文章主要為大家詳細介紹了python如何實現(xiàn)對EXCEL數(shù)據(jù)進行讀取和寫入，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2022-04-04
python開發(fā)入門——列表生成式
這篇文章主要介紹了python 列表生成式的相關資料，幫助大家更好的理解和學習python開發(fā)，感興趣的朋友可以了解下
2020-09-09
Python實現(xiàn)把數(shù)字轉(zhuǎn)換成中文
這篇文章主要介紹了Python實現(xiàn)把數(shù)字轉(zhuǎn)換成中文,一般用于數(shù)字金額轉(zhuǎn)中文大寫金額,即將阿拉伯數(shù)字轉(zhuǎn)換為大寫的中文,需要的朋友可以參考下
2015-06-06
Python如何將bmp格式的圖片批量轉(zhuǎn)成jpg
這篇文章主要介紹了Python如何將bmp格式的圖片批量轉(zhuǎn)成jpg問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2023-03-03
Python 逐行分割大txt文件的方法
本文通過代碼給大家介紹了Python 逐行分割大txt文件的方法，在文中給大家提到了Python從txt文件中逐行讀取數(shù)據(jù)的方法，需要的朋友參考下吧
2017-10-10
基于python進行抽樣分布描述及實踐詳解
這篇文章主要介紹了基于python進行抽樣分布描述及實踐詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
2019-09-09
Python實現(xiàn)一個簡單的QQ截圖
大家好，本篇文章主要講的是Python實現(xiàn)一個簡單的QQ截圖，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下的相關資料
2022-02-02
python目標檢測基于opencv實現(xiàn)目標追蹤示例
這篇文章主要為大家介紹了python基于opencv實現(xiàn)目標追蹤示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
2022-05-05
python為tornado添加recaptcha驗證碼功能
tornado作為微框架，并沒有自帶驗證碼組件，recaptcha是著名的驗證碼解決方案，簡單易用，被很多公司運用來防止惡意注冊和評論。tornado添加recaptchaHA非常容易
2014-02-02
python 基于opencv實現(xiàn)高斯平滑
這篇文章主要介紹了python 基于opencv實現(xiàn)高斯平滑，幫助大家更好的理解和使用python處理圖片，感興趣的朋友可以了解下
2020-12-12