二分搜尋演算法(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
查看全部
你可能也想看
Google News 追蹤
*合作聲明與警語：
本文係由國泰世華銀行邀稿。
證券服務係由國泰世華銀行辦理共同行銷證券經紀開戶業務，定期定額(股)服務由國泰綜合證券提供。
剛出社會的時候，很常在各種 Podcast 或 YouTube 甚至是在朋友間聊天，都會聽到各種市場動態、理財話題，像是：聯準會降息或是近期哪些科
這篇文章，會帶著大家複習以前學過的二分搜尋法(Binary Search)框架，
並且以二分搜尋法的概念為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個實用的演算法框架。
Binary search 二分搜尋法框架
用途:
在已經排序好的數列中尋找目標值。
題目敘述
題目會給定一個輸入陣列piles，代表每堆香蕉所擁有的香蕉數量，和
一個時間上限h小時。
Koko喜歡吃香蕉，每小時可以吃k個香蕉，請問k值最少需要多少，才能讓Koko在h小時內吃完所有的香蕉？
題目的原文敘述
測試範例
Example 1:
Input: piles =
題目敘述
題目會給定一個猜數字的場景和介面
(包含一個可以呼叫，驗證是否為答案的API guess() function)，
要求我們實現猜數字的function guessNumber(int n)。
題目已經事先設定好一個祕密數字，要求我們去找出來那個祕密數字是多少。
就好像小時候
題目會給我們一個山形的輸入陣列，和目標值target，要求我們找出目標值所在的陣列索引。如果出現兩次，返回比較小的那一個，也就是比較靠左的那個索引值。
山形的意思就是說，從最左側到山頂最大值都是遞增，從山頂最大值到右側都是遞減。
題目會給我們一個排序好的陣列，還有一個目標值target
要求我們在陣列中尋找target所在的索引位置。
如果target 不存在，返回-1
題目要求必須在O( log n )對數時間內完成 。
關於需要依附於任何人作為Projector的問題？這取決於你的設計，如果你是一個一份人的定義，不需要。好吧，如果你是二份人的，你必須要有一個人。所以有兩種夥伴。有永久性的，也有臨時性的。而事實是，那是一個二份人的定義。你有哪一個並不重要。它不像你必須一直有永久的聯繫，同一個人，它沒有。
以上述傳統作為參照基準，聖俗二分的觀念與我們的信仰違背。先針對「上帝就如流亡國王」的誤解來澄清。在這個錯誤的比喻當中，聖潔的上帝、天國的管治遭受造物排拒，受造界成為抵擋上帝的世俗勢力範圍，這就是所謂的聖俗二分。
這種聖俗二分的觀念與我們的信仰相違背，以傳統作為參照基準就可以見得。
傳統的其中一個例子是《西敏信條》（Westminster Confession of Faith）。十七世紀中期，英國內戰爆發，民不聊生，社會、政治、甚至宗教體制岌岌可危。
二次大戰打得正慘烈的時候，德國心理學家昆柯（Fritz Künkel）在美國出版《追求成熟》（In Search of Maturity）。這本心理學作品筆調樸實、看待人性合乎中道，更嘗試與基督信仰相調和。
*合作聲明與警語：
本文係由國泰世華銀行邀稿。
證券服務係由國泰世華銀行辦理共同行銷證券經紀開戶業務，定期定額(股)服務由國泰綜合證券提供。
剛出社會的時候，很常在各種 Podcast 或 YouTube 甚至是在朋友間聊天，都會聽到各種市場動態、理財話題，像是：聯準會降息或是近期哪些科
這篇文章，會帶著大家複習以前學過的二分搜尋法(Binary Search)框架，
並且以二分搜尋法的概念為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個實用的演算法框架。
Binary search 二分搜尋法框架
用途:
在已經排序好的數列中尋找目標值。
題目敘述
題目會給定一個輸入陣列piles，代表每堆香蕉所擁有的香蕉數量，和
一個時間上限h小時。
Koko喜歡吃香蕉，每小時可以吃k個香蕉，請問k值最少需要多少，才能讓Koko在h小時內吃完所有的香蕉？
題目的原文敘述
測試範例
Example 1:
Input: piles =
題目敘述
題目會給定一個猜數字的場景和介面
(包含一個可以呼叫，驗證是否為答案的API guess() function)，
要求我們實現猜數字的function guessNumber(int n)。
題目已經事先設定好一個祕密數字，要求我們去找出來那個祕密數字是多少。
就好像小時候
題目會給我們一個山形的輸入陣列，和目標值target，要求我們找出目標值所在的陣列索引。如果出現兩次，返回比較小的那一個，也就是比較靠左的那個索引值。
山形的意思就是說，從最左側到山頂最大值都是遞增，從山頂最大值到右側都是遞減。
題目會給我們一個排序好的陣列，還有一個目標值target
要求我們在陣列中尋找target所在的索引位置。
如果target 不存在，返回-1
題目要求必須在O( log n )對數時間內完成 。
關於需要依附於任何人作為Projector的問題？這取決於你的設計，如果你是一個一份人的定義，不需要。好吧，如果你是二份人的，你必須要有一個人。所以有兩種夥伴。有永久性的，也有臨時性的。而事實是，那是一個二份人的定義。你有哪一個並不重要。它不像你必須一直有永久的聯繫，同一個人，它沒有。
以上述傳統作為參照基準，聖俗二分的觀念與我們的信仰違背。先針對「上帝就如流亡國王」的誤解來澄清。在這個錯誤的比喻當中，聖潔的上帝、天國的管治遭受造物排拒，受造界成為抵擋上帝的世俗勢力範圍，這就是所謂的聖俗二分。
這種聖俗二分的觀念與我們的信仰相違背，以傳統作為參照基準就可以見得。
傳統的其中一個例子是《西敏信條》（Westminster Confession of Faith）。十七世紀中期，英國內戰爆發，民不聊生，社會、政治、甚至宗教體制岌岌可危。
二次大戰打得正慘烈的時候，德國心理學家昆柯（Fritz Künkel）在美國出版《追求成熟》（In Search of Maturity）。這本心理學作品筆調樸實、看待人性合乎中道，更嘗試與基督信仰相調和。