基本演算法介紹-搜尋

搜尋(search) 演算法

搜尋(search) 演算法:在大量資料中找出目標資料的演算法

(1)日常生活的應用

例如從通訊錄找出某好友的電話號碼、利用電話號碼或身分證，找出會員資料或是從字典中查詢某一個單字

(2)搜尋(search) 演算法種類

最常用的搜尋演算法有循序搜尋法(Sequential Search)和二分搜尋法(Binary Search) 。

循序搜尋法(Sequential Search)

循序搜尋法算是搜尋演算法當中比較簡單的一種，用來達成搜尋特定資料之用。它是從第一個資料開始取出，依序慢慢的逐個與「目標資料」相互比較，直到找到所要的元素或所有資料均尋找完為止。即從頭到尾一一比較各點 data 值，直到找到、或搜尋完整個範圍仍找不到為止

範例

(1)Pokemons 這一排櫃子裡有4隻神奇寶貝，假設每個櫃子的門都被關上，我們事前也不知道各個神奇寶貝的位置，這時如果想要知道「比獸」神奇寶貝在哪裡時，我們第一個想到的方法會是什麼呢？ 最直觀地想，我們會從第一個櫃子開始試，一次開一個櫃子，直到找到「呆獸」為止。像這樣的搜尋方法，就是最經典簡單的「簡易搜尋」。

(2)在一副打亂的撲克牌中，如果我們要找尋紅心大老二，我們可以從第一張、第二張、依序搜尋，直到找到這張牌或是撲克牌已經用盡為止，這種搜尋方式稱為循序搜尋法。

A.圖解

首先，我們將搜尋問題簡化為數字的搜尋。假設原始資料有：5、8、10、1、7 這 5 個隨機數字，搜尋的目標資料是 10，因為原始資料只有 5 個數字，所以你能夠一眼就看到 10 在原始資料的第 3 筆，但是如果資料量暴增到 100 個，你就得要從解決問題的過程中找出規則，將其發展成一套搜尋演算法，而這套演算法適用於各種大小的資料量與各種不同的目標資料。

B.影片(看30秒)

活動設計-循序搜尋法(Sequence Search.Linear Search)

思考問題

想想看此類循序搜尋法有何特色呢?

說明

循序搜尋演算法依序取出表列的資料，比較鍵值，如果比對成功則回傳此筆表列的資料(item)，如果比對不成功則依序取出下一筆表列的資料。假如搜尋表列有 n 筆資

料，且待查詢的鍵值都在此表列中，則最好的情況是第一次就找到，最差的情況是最 後一次才找到，當 n 值很大的時候，例如 1,000,000 筆資料，平 均搜尋的就要 50 萬次，

搜尋時間就相對較長。

循序搜尋法(Sequential Search)實作篇(此為高一課綱.但簡單可實作)

Scratch

http://usr.nkust.org/2018/06/12/scratch-sequential-search/