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

gotham 發(fā)布于2019-07-31 10:07 / 2606人閱讀

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

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

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

有序數(shù)據(jù)結(jié)構(gòu)：棧、隊列、鏈表。有序數(shù)據(jù)結(jié)構(gòu)省空間（儲存空間小）

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

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

樹、堆

圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

加密算法：

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

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

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

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

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

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

    if(guess === item) { // 找到元素
      return mid
    }
    if(guess > item) { // 猜測的數(shù)大了
      high = mid - 1
    } else {　// 猜測的數(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))

找一個平衡二叉樹最后一個節(jié)點

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

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

即：?。驳模反畏?= 100

簡單查找時間是　ｙ= ax 的線性方方程
所以很容易得出結(jié)論

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

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

大O符號

大O符號中指定的算法的增長順序

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

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

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

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

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

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

小結(jié)

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

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

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

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

快速排序

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

快排大概的流程是：

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

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

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

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

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

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

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

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

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

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

常見練習(xí)

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

參考

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

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

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

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

發(fā)表評論

登陸后可評論

0條評論

gotham

男|高級講師

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

TA的文章

項目中引入特殊字體【小程序、h5】包括canvas畫圖

閱讀 3191·2019-08-30 15:55
前端代碼集

閱讀 2953·2019-08-30 13:46
Chrome, vh Is Always Calculated as If the Url Bar

閱讀 1455·2019-08-29 17:29
移動前端知識總結(jié)

閱讀 3524·2019-08-29 11:08
從一滴水說起，談?wù)凜SS形狀的生成思路

閱讀 3449·2019-08-29 11:04
CSS中那些微妙模糊的屬性

閱讀 1096·2019-08-28 18:20
React項目中碰到的IE問題

閱讀 553·2019-08-26 13:37
freeCodeCamp 學(xué)習(xí)記錄——初級算法「01」翻轉(zhuǎn)字符串

閱讀 1340·2019-08-26 11:49

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

資訊專欄INFORMATION COLUMN

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

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

相關(guān)文章