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

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

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

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

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

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

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

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

樹(shù)、堆

圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

加密算法：

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

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

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

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

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

  while(low <= high) { // 只要范圍沒(méi)有縮小到只包含一個(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è)平衡二叉樹(shù)最后一個(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!)，這樣的算法包括接下來(lái)將介紹的旅行商問(wèn)題的解決方案——一種非常慢的算法

小結(jié)

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

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

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

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

快速排序

快排和二分查找都基于一種叫做「分治」的算法思想，通過(guò)對(duì)數(shù)據(jù)進(jìn)行分類(lèi)處理，不斷降低數(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)過(guò)一次循環(huán)之后，A 左邊為小于 A 的，右邊為大于 A 的

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

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

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

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

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

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

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

常見(jiàn)練習(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