數(shù)據(jù)結(jié)構(gòu)與算法：二分查找

you_De 發(fā)布于2019-08-16 15:26 / 1985人閱讀

摘要：為檢查長(zhǎng)度為的列表，二分查找需要執(zhí)行次操作。最后需要指出的一點(diǎn)是高水平的讀者可研究一下二叉樹關(guān)于二叉樹，戳這里數(shù)據(jù)結(jié)構(gòu)與算法二叉樹算法常見練習(xí)在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。

常見數(shù)據(jù)結(jié)構(gòu)

簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)（必須理解和掌握）

有序數(shù)據(jù)結(jié)構(gòu)：棧、隊(duì)列、鏈表。有序數(shù)據(jù)結(jié)構(gòu)省空間（儲(chǔ)存空間?。?/p>

無序數(shù)據(jù)結(jié)構(gòu)：集合、字典、散列表，無序數(shù)據(jù)結(jié)構(gòu)省時(shí)間（讀取時(shí)間快）

復(fù)雜數(shù)據(jù)結(jié)構(gòu)

樹、堆

圖

本系列主要內(nèi)容

數(shù)組和列表：最常用的數(shù)據(jù)結(jié)構(gòu)

與鏈表相比，數(shù)組具有更好的緩存位置。

棧和隊(duì)列：與列表類似但是更復(fù)雜數(shù)據(jù)結(jié)構(gòu)

鏈表：如何通過它們克服數(shù)組的不足，

鏈表允許在迭代期間有效地從序列中的任何位置插入或刪除元素。

鏈表的一個(gè)缺點(diǎn)是訪問時(shí)間是線性的(而且難以管道化)。（更快的訪問，如隨機(jī)訪問，是不可行的）

字典：將數(shù)據(jù)以鍵-值對(duì)的的形式儲(chǔ)存

散列(表)：適用于快速查找和檢索

集合：適用于存儲(chǔ)只出現(xiàn)一次的元素

二叉樹：以層級(jí)的形式存儲(chǔ)數(shù)據(jù)

圖和圖算法：網(wǎng)絡(luò)建模的理想選擇

算法：包括排序、搜索、圖形算法

高級(jí)算法：動(dòng)態(tài)規(guī)劃、貪心算法、BF、分治、回溯等算法范式

加密算法：

有序數(shù)據(jù)結(jié)構(gòu) 數(shù)組 列表棧 隊(duì)列 鏈表 無序列數(shù)據(jù)結(jié)構(gòu) 集合字典 散列(表) 簡(jiǎn)單算法 => 二分查找

二分查找是搜索算法中的一種，用來搜索有序數(shù)組

二分查找：是一種簡(jiǎn)單算法，其輸入是一個(gè)有序的元素列表（必須有序的原因稍后解釋）。如果要
查找的元素包含在列表中，二分查找返回其位置；否則返回null。

Javascript ES6實(shí)現(xiàn) 非遞歸的

/** 
 * 函數(shù)binarySearch接受一個(gè)有序數(shù)組和一個(gè)元素。 如果指定的元素包含在數(shù)組中， 這個(gè)
 函數(shù)將返回其位置。 你將跟蹤要在其中查找的數(shù)組部分—— 開始時(shí)為整個(gè)數(shù)組。
*/
const binarySearch = (list, item) => {
  // 數(shù)組要查找的范圍
  // low、high用于跟蹤要在其中查找的列表部分
  let low = 0  
  let high = list.length - 1

  while(low <= high) { // 只要范圍沒有縮小到只包含一個(gè)元素
    const mid = Math.floor((low + high) / 2)
    const guess = list[mid] // 找到中間的元素

    if(guess === item) { // 找到元素
      return mid
    }
    if(guess > item) { // 猜測(cè)的數(shù)大了
      high = mid - 1
    } else {　// 猜測(cè)的數(shù)小了
      low = mid + 1
    }
  }

  return null
}

const myList = [1, 3, 5, 7, 9]

console.log(binarySearch(myList, 3))
console.log(binarySearch(myList, -1))

遞歸的

 
const binarySearch = (list, item, low, hight) => {
  let arrLength = list.length
  while (low <= high) {
    let mid = Math.floor((low + high) / 2)
    let guess = list[mid]

    if( guess === item ) {
      return mid
    } else if (guess > item) {
      high = mid - 1
      list = list.slice(0, mid)
      return binarySearch(list, item, low, high)
    } else {
      low = mid + 1
      list = list.slice(low, arrLength)
      return binarySearch(list, item, low, high)
    }
  }
  return null 
}

const createArr = (n) => Array.from({length: n}, (v, k) => k + 1)

const myList = createArr(100)
let low = 0
let high = myList.length - 1

console.log(binarySearch(myList, 3, low, high))
console.log(binarySearch(myList, -1, low, high))

找一個(gè)平衡二叉樹最后一個(gè)節(jié)點(diǎn)

Python實(shí)現(xiàn) 運(yùn)行時(shí)間(時(shí)間復(fù)雜度)

二分查找的運(yùn)行時(shí)間為對(duì)數(shù)時(shí)間（或log時(shí)間）。
如果列表包含100個(gè)元素，最多要猜7次；如果列表包含40億個(gè)數(shù)字，最多
需猜32次。

即：　２的７次方 = 100

簡(jiǎn)單查找時(shí)間是?。? ax 的線性方方程
所以很容易得出結(jié)論

隨著元素?cái)?shù)量的增加（ｘ增加），二分查找需要的時(shí)間（ｙ）并不多， 而簡(jiǎn)單查找需要的時(shí)間（ｙ）卻很多。
因此，隨著列表的增長(zhǎng)，二分查找的速度比簡(jiǎn)單查找快得多。

為檢查長(zhǎng)度為n的列表，二分查找需要執(zhí)行l(wèi)og n次操作。使用大O表示法，
這個(gè)運(yùn)行時(shí)間怎么表示呢？O(log n)。一般而言，簡(jiǎn)單算法的大O表示法像下面這樣

大O符號(hào)

大O符號(hào)中指定的算法的增長(zhǎng)順序

以下是一些最常用的 大O標(biāo)記法 列表以及它們與不同大小輸入數(shù)據(jù)的性能比較。

O(log n)，也叫對(duì)數(shù)時(shí)間，這樣的算法包括二分查找

O(n)，也叫線性時(shí)間，這樣的算法包括簡(jiǎn)單查找。

O(n * log n)，這樣的算法包括快速排序——一種速度較快的排序算法。

,這樣的算法包括選擇排序——一種速度較慢的排序算法

O(n!)，這樣的算法包括接下來將介紹的旅行商問題的解決方案——一種非常慢的算法

小結(jié)

算法的速度指的并非時(shí)間，而是操作數(shù)的增速。

談?wù)撍惴ǖ乃俣葧r(shí)，我們說的是隨著輸入的增加，其運(yùn)行時(shí)間將以什么樣的速度增加。

算法的運(yùn)行時(shí)間用大O表示法表示。

O(log n)比O(n)快，當(dāng)需要搜索的元素越多時(shí)，前者比后者快得越多

快速排序

快排和二分查找都基于一種叫做「分治」的算法思想，通過對(duì)數(shù)據(jù)進(jìn)行分類處理，不斷降低數(shù)量級(jí)，實(shí)現(xiàn)O(logN)（對(duì)數(shù)級(jí)別，比O(n) 這種線性復(fù)雜度更低的一種，快排核心是二分法的O(logN) ，實(shí)際復(fù)雜度為O(N*logN) ）的復(fù)雜度。

快排大概的流程是：

隨機(jī)選擇數(shù)組中的一個(gè)數(shù) A，以這個(gè)數(shù)為基準(zhǔn)

其他數(shù)字跟這個(gè)數(shù)進(jìn)行比較，比這個(gè)數(shù)小的放在其左邊，大的放到其右邊

經(jīng)過一次循環(huán)之后，A 左邊為小于 A 的，右邊為大于 A 的

這時(shí)候?qū)⒆筮吅陀疫叺臄?shù)再遞歸上面的過程

旅行商問題--復(fù)雜度O(n!)的算法

簡(jiǎn)單的講如果旅行者要去５個(gè)城市，先后順序確定有５＊４＊３＊２＊１　＝?。保玻胺N排序。（這種排序想想高中時(shí)候?qū)W到過的排序知識(shí)）

推而廣之,涉及n個(gè)城市時(shí),需要執(zhí)行n!(n的階乘)次操作才能計(jì)算出結(jié)果。因此運(yùn)行時(shí)間
為O(n!),即階乘時(shí)間。除非涉及的城市數(shù)很少,否則需要執(zhí)行非常多的操作。如果涉及的城市
數(shù)超過100,根本就不能在合理的時(shí)間內(nèi)計(jì)算出結(jié)果——等你計(jì)算出結(jié)果,太陽都沒了。

這種算法很糟糕!,可別無選擇。這是計(jì)算機(jī)科學(xué)領(lǐng)域待解的問題之一。對(duì)于這個(gè)問題,目前還沒有找到更快的算法,有些很聰明的人認(rèn)為這個(gè)問題根本就沒有更巧妙的算法。
面對(duì)這個(gè)問題,我們能做的只是去找出近似答案。

最后需要指出的一點(diǎn)是,高水平的讀者可研究一下二叉樹

關(guān)于二叉樹，戳這里: 數(shù)據(jù)結(jié)構(gòu)與算法:二叉樹算法

常見練習(xí)

在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。

參考

算法圖解
JavaScript 算法與數(shù)據(jù)結(jié)構(gòu)
https://github.com/egonSchiel...
【算法】時(shí)間復(fù)雜度
【算法】空間復(fù)雜度
InterviewMap 時(shí)間復(fù)雜度
https://github.com/trekhleb/j...
每周一練之數(shù)據(jù)結(jié)構(gòu)與算法（Stack）
All Algorithms implemented in Python

GPU云服務(wù)器云服務(wù)器二分查找二分查找代碼二分法查找二分查找c語言實(shí)例

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/73484.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

you_De

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

bazel編譯tensorflow

閱讀 1608·2023-04-26 01:54
酷銳云：國慶特惠，香港美國10M帶寬，月付19元，香港美國CN2GIA，月付27元起

閱讀 1637·2021-09-30 09:55
虛擬主機(jī)被攻擊怎么辦-服務(wù)器被黑客攻擊怎么辦？

閱讀 2658·2021-09-22 16:05
快快云-海外優(yōu)質(zhì)服務(wù)器商家！香港沙田CN2、美國Cera大寬帶、日本CN2均為三網(wǎng)直連CN2 GIA

閱讀 1873·2021-07-25 21:37
CSS實(shí)現(xiàn)模擬float: center文字左右環(huán)繞圖片的效果

閱讀 2633·2019-08-29 18:45
前端每日實(shí)戰(zhàn)：136# 視頻演示如何用 D3 和 GSAP 創(chuàng)作一個(gè)橫條 loader

閱讀 1900·2019-08-29 16:44
前端空間 - 收藏集 - 掘金

閱讀 1895·2019-08-29 12:34
實(shí)現(xiàn)菜單下拉伸展折疊效果demo

閱讀 1359·2019-08-23 14:02

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購！

數(shù)據(jù)結(jié)構(gòu)與算法：二分查找

相關(guān)文章