二分搜尋演算法(Binary Search)

2023/04/09閱讀時間約 2 分鐘

假設有天你要在電話簿找一個K開頭的人，或是O開頭的人你並不會從A開始找一定是從最接近的開始找。

二分搜尋是一種演算法

下方是二分搜尋演算法的如何作用

STEP 1

圖一這是一組陣列，由小到大排列，其中我們在這陣列要找的數字是“13”所以我們必須把它存在 searchForNumber 這個變數裡面 (變數是關聯一個資料型態、儲存的值與儲存空間的位址值)

let searchForNumber = 13

圖一

STEP 2

尋找裡數字最大的跟數字最小的，當想取得中間值就可以使用(LOW+HIGH)/2

黃色是最小的數字綠色是中間數字紅色是最大的數字

現在可以開始使用二分搜尋

STEP 3 二分搜尋例子

let findBinary = function (list, targe) {
　　let low = 0;
　　let high = list.length - 1;  // 抓取二分搜尋最大跟最小的長度
　　while (low <= high) { // 為了可以不斷地縮小範圍尋找
　　　　let mid = Math.floor((low + high) / 2);
　　　　let guess = list[mid]
　　　　if (guess === targe) {
　　　　　　return mid
　　　　}
　　　　if (guess > targe) {
　　　　　　high = mid - 1;
　　　　} else {
　　　　　　low = mid + 1;
　　　　}
　　}
　　return null
}
findBinary([2,3,6,8,9,13,20],13) // index = 5

　　 index
[2] = 0
[3] = 1
[6] = 2
[8] = 3
[9] = 4
[13] = 5
[20] = 6

STEP 4

結論就會是上方的第五個index

1會員

1內容數

留言0

查看全部

發表第一個留言支持創作者！

你可能也想看

創作者要怎麼好好休息 + 避免工作過量？《黑貓創作報#4》午安，最近累不累？這篇不是虛假的關心。而是《黑貓創作報》發行以來可能最重要的一篇。是的，我們這篇講怎麼補充能量，也就是怎麼休息。

黑貓老師

2024-06-29

#創作 #作者 #社群

防曬產品係數測試報告彙整(2024年)從2014年起，自己對於市售防曬產品的效能產生了濃厚的興趣。因為當時候發現不少產品的防曬係數其實標示是有問題的，像是原本應該是人體測試的SPF與PA數值，實際上沒有做，只用機器測試的數據來充當，但這兩者卻有很大的差異。像是防曬係數其實有強度、廣度與平均度三個面向需要一起判斷，但多數廠商並沒有完整標示

邱品齊皮膚科醫師

2023-04-27

#防曬 #檢測 #防曬係數

合縱連橫: 二分搜尋法框架_理解背後的本質這篇文章，會帶著大家複習以前學過的二分搜尋法(Binary Search)框架，並且以二分搜尋法的概念為核心，貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個實用的演算法框架。 Binary search 二分搜尋法框架用途: 在已經排序好的數列中尋找目標值。

小松鼠

2024-03-19

#leetcode #algorithm #python

二分搜尋: Koko吃香蕉 Koko Eating Bananas_Leetcode #875 精選75題題目敘述題目會給定一個輸入陣列piles，代表每堆香蕉所擁有的香蕉數量，和一個時間上限h小時。 Koko喜歡吃香蕉，每小時可以吃k個香蕉，請問k值最少需要多少，才能讓Koko在h小時內吃完所有的香蕉？題目的原文敘述測試範例 Example 1: Input: piles =

小松鼠

2024-02-26

#python #leetcode #algorithm

遊戲模擬+二分搜尋法: 猜數字Guess Number_Leetcode #374 精選75題題目敘述題目會給定一個猜數字的場景和介面 (包含一個可以呼叫，驗證是否為答案的API guess() function)，要求我們實現猜數字的function guessNumber(int n)。題目已經事先設定好一個祕密數字，要求我們去找出來那個祕密數字是多少。就好像小時候

小松鼠

2024-02-14

#leetcode #python #algorithm

一魚多吃用二分搜尋法找目標值 Find in Mountain Array_Leetcode #1095題目會給我們一個山形的輸入陣列，和目標值target，要求我們找出目標值所在的陣列索引。如果出現兩次，返回比較小的那一個，也就是比較靠左的那個索引值。山形的意思就是說，從最左側到山頂最大值都是遞增，從山頂最大值到右側都是遞減。

小松鼠

2023-10-13

#binarysearch #二分搜尋 #最大值

基本搜尋演算法二分搜尋法 Binary Search_Leetcode 704題目會給我們一個排序好的陣列，還有一個目標值target 要求我們在陣列中尋找target所在的索引位置。如果target 不存在，返回-1 題目要求必須在O( log n )對數時間內完成。

小松鼠

2023-09-22

#binarysearch #二分搜尋 #二元搜尋

二份人的定義和他們的兩種夥伴關於需要依附於任何人作為Projector的問題？這取決於你的設計，如果你是一個一份人的定義，不需要。好吧，如果你是二份人的，你必須要有一個人。所以有兩種夥伴。有永久性的，也有臨時性的。而事實是，那是一個二份人的定義。你有哪一個並不重要。它不像你必須一直有永久的聯繫，同一個人，它沒有。