數據結構與算法：二分查找

you_De 發布于2019-08-16 15:26 / 1975人閱讀

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

常見數據結構

簡單數據結構（必須理解和掌握）

有序數據結構：棧、隊列、鏈表。有序數據結構省空間（儲存空間?。?/p>

無序數據結構：集合、字典、散列表，無序數據結構省時間（讀取時間快）

復雜數據結構

樹、堆

圖

本系列主要內容

數組和列表：最常用的數據結構

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

棧和隊列：與列表類似但是更復雜數據結構

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

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

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

字典：將數據以鍵-值對的的形式儲存

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

集合：適用于存儲只出現一次的元素

二叉樹：以層級的形式存儲數據

圖和圖算法：網絡建模的理想選擇

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

高級算法：動態規劃、貪心算法、BF、分治、回溯等算法范式

加密算法：

有序數據結構 數組列表棧隊列鏈表 無序列數據結構 集合字典 散列(表) 簡單算法 => 二分查找

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

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

Javascript ES6實現 非遞歸的

/** 
 * 函數binarySearch接受一個有序數組和一個元素。 如果指定的元素包含在數組中， 這個
 函數將返回其位置。 你將跟蹤要在其中查找的數組部分—— 開始時為整個數組。
*/
const binarySearch = (list, item) => {
  // 數組要查找的范圍
  // 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) { // 猜測的數大了
      high = mid - 1
    } else {　// 猜測的數小了
      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))

找一個平衡二叉樹最后一個節點

Python實現 運行時間(時間復雜度)

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

即：　２的７次方 = 100

簡單查找時間是?。? ax 的線性方方程
所以很容易得出結論

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

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

大O符號

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

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

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

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

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

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

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

小結

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

談論算法的速度時，我們說的是隨著輸入的增加，其運行時間將以什么樣的速度增加。

算法的運行時間用大O表示法表示。

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

快速排序

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

快排大概的流程是：

隨機選擇數組中的一個數 A，以這個數為基準

其他數字跟這個數進行比較，比這個數小的放在其左邊，大的放到其右邊

經過一次循環之后，A 左邊為小于 A 的，右邊為大于 A 的

這時候將左邊和右邊的數再遞歸上面的過程

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

簡單的講如果旅行者要去５個城市，先后順序確定有５＊４＊３＊２＊１　＝　１２０種排序。（這種排序想想高中時候學到過的排序知識）

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

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

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

關于二叉樹，戳這里: 數據結構與算法:二叉樹算法

常見練習

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

參考

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

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/73484.html

數據結構與算法——二分查找

摘要：所以，二分查找較適用于一次排序，多次查找的數據。面對大量的數據，二分查找方能體現其優勢。 1. 二分查找的思想二分查找是一種使用十分普遍的查找算法，其基本的思路也非常的簡單，在一個有序的數據集合中，我們想要查找某個數據，直接取最中間的那個數據，將它和要找的數據進行比較，如果較大，則在更大的那個數值區間繼續取中間值查找，反之亦然。例如我們要在一個有序的集合里[1，3，5，6，7，8，...

boredream 2019-08-16 16:02 評論0 收藏0
數據結構與算法：二分查找

摘要：為檢查長度為的列表，二分查找需要執行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關于二叉樹，戳這里數據結構與算法二叉樹算法常見練習在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。常見數據結構簡單數據結構（必須理解和掌握）有序數據結構：棧、隊列、鏈表。有序數據結構省空間（儲存空間小）無序數據結構：集合、字典、散列表，無序...

zsirfs 2019-08-23 15:33 評論0 收藏0
數據結構與算法：二分查找

摘要：為檢查長度為的列表，二分查找需要執行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關于二叉樹，戳這里數據結構與算法二叉樹算法常見練習在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。常見數據結構簡單數據結構（必須理解和掌握）有序數據結構：棧、隊列、鏈表。有序數據結構省空間（儲存空間小）無序數據結構：集合、字典、散列表，無序...

gotham 2019-07-31 10:07 評論0 收藏0
【二分查找】| 模擬 20 萬數據快速查詢 IP 歸屬地

摘要：通過兩個二分查找的條件繼續進行問題的分析，那么問題又來了，二分查找是快速的查找一個數據是否存在一組數據中，而且效率極高，億查找一個數據只需次查找。二分查找的三點重點循環退出條件注意是而不是。 showImg(https://segmentfault.com/img/remote/1460000018761246);這篇文章主要深入數據結構與算法在解決實際問題怎么運用和分析的，對于 IP...

The question 2019-08-23 16:44 評論0 收藏0
數據結構與算法——二分查找練習

摘要：查找最后一個等于給定值的元素這種變形的二分查找和上面的這種情況很類似，還是利用上面的那個數組，我們要查找最后一個等于的元素。 1. 概述前面說到了二分查找問題，看起來非常的簡單，的確，前面的兩種實現都不難，代碼也很容易寫，因為那只是最基礎的二分查找問題了。今天來看看幾種稍微復雜的二分查找問題：查找第一個等于給定值的元素查找最后一個等于給定值的元素查找第一個大于等于給定值的元素...

JasinYip 2019-08-16 16:05 評論0 收藏0