iT邦幫忙

0

【演算法筆記】白話文聊聊什麼是線性搜尋(linear search)與二分搜尋?(binary search)

由於二分搜尋(binary search)這個概念在資工領域裡還蠻常出現的,
將概念記錄一下以做備忘

首先,我們思考一個情境:
假設現在大學英文科期末考剛考完,
你要去找你的助教領取考卷,
但是你的助教說他很忙,
考卷就放在隔壁的桌上,
請你自己去找,
那麼你該如何找到你的考卷呢?
(假設你的名字是John,考卷有200張)

線性搜尋(linear search)

最簡單的方法就是你一張張的把考卷拿起來看,
看到第一張考卷的名字是Andy,不是自己的的考卷…
再看第二張考卷的名字是Annie,不是自己的考卷…

如此檢查下去,
你最多把200張考卷都看完後,
你就能夠找到自己的考卷了

二分搜尋(binary search)- 僅適用在排序過的物件中尋找

你正想繼續檢查全部的考卷,
這時你的助教告訴你,
考卷的順序已經按照英文字母的順序(abc...z)排過了,
那麼你有沒有更聰明的方式去找你的考卷呢?

這時你就可以直接從中間的地方開始找,
比如說看第100張考卷好了,
假設第100張考卷上的名字的Leon
這時你想: 英文字母J排在L的前面,
所以你的考卷一定是在前面100張裡面,
一下子你就可以少看一半的考卷了

再從一半的地方看,
比如說第50張考卷上的名字是Fiona
因為英文字母J排在F的後面,
所以你知道考卷一定是放在第51~99的位置,
如此反覆找下去,
每次都可以少搜索一半的數量,
可以大大的節省找東西的時間

在一堆排序過的物件中,
每次從中間的地方開始搜索的方法即為二分搜尋法


尚未有邦友留言

立即登入留言