題組內容

2. 下列為線性搜尋演算法之虛擬碼,其中變數 n 為資料個數、陣列 S [ ] 為資料陣列、變數 key 為欲搜尋的目標資料, 找到目標資料時,將回傳該資料位於此陣列的哪一個位置,若找不到目標資料時,則回傳-1,請回答以下問題。
66333c90737be.jpg

(1)假設共有 n 筆資料,則其平均比較次數為多少次? 試證明之。 (2 分)