iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 23
1
Software Development

前端工程師用 javaScript 學演算法系列 第 23

簡易搜尋 Sequential Search & 二分搜尋 Binary Search

基本上這篇文章介紹的兩種搜尋都在第三天評量演算法好壞的 Big O出現過,但本篇會著重在程式部分。


Big O(n): 簡易搜尋 Sequential Search

執行時間會跟著 n 等比例變多
https://ithelp.ithome.com.tw/upload/images/20190904/20106426j2AgPmlqeJ.jpg
我現在想吃 Grapes,但每個水果都被關在一模一樣的不透明箱子裡,所以我只好一個一個打開來檢查。

let fruits= ['Banana', 'Grapes', 'Watermelon', 'Avocado'];
for(let i = 0; i < fruits.length; i++){
	if(fruits[i] == 'Grapes'){
		console.log('耶 找到了')
	}else{
	  console.log('繼續找下一個箱子吧')
	}
}

Big O(log n): 二分搜尋 Binary Search

輸入數量 n 時,執行步驟是 log n。
Binary Search 是非常常見的考題之一,概念不會太難,而且效能相當不錯。只有一個地方要注意就是要使用它,input 必須是要排序好的 (ex. 暗箱是 a-z )

觀察步驟

步驟一 選擇中間值

  • 目標值 == 選取值 ,則結束搜尋
  • 目標值 < 選取值,則返回步驟一在選取值左邊子陣列中繼續尋找
  • 目標值 > 選取值 ,則返回步驟一在選取值右邊子陣列中繼續尋找

實際操作

這邊用一樣的水果例子。現在有 9 個箱子依字母順序排好 (例如 A 開頭水果一定會排在其他字母開頭水果前面)。我想要找到 Grape 最少幾次就可以找到呢 ?
https://ithelp.ithome.com.tw/upload/images/20190904/20106426FmkbmndszJ.jpg
先從中間的箱子開始找,找到 pineapple,而 G 字母比 P 前面所以往前找

// 這邊都以 index 為單位
let start = 0;
let end = fruitArray.length - 1;
let mid;
 
//  從中間開始切
let mid = Math.floor( (start + end ) / 2)  // 找到 P

https://ithelp.ithome.com.tw/upload/images/20190904/20106426hjSdHfE9rX.jpg
再從左半邊中間位置找,打開發現是 Banana,而 G 比 B 後面所以往後找

if(target < fruitArray[mid]){
  // 往左找
  end = mid - 1;
}else if(target > fruitArray[mid]){
	// 往右找
  start = mid + 1
}else{
  return mid;
};

https://ithelp.ithome.com.tw/upload/images/20190904/201064267Wf9NNhMw4.jpg
一樣的方法再從中間找,打開發現是 Cherry,G 比 C 後面所以往後找
https://ithelp.ithome.com.tw/upload/images/20190904/201064261Hb84xj7DZ.jpg
找到囉 !

完整程式碼

function binarySearch(fruitArray, target){
  
  // 這邊都以 index 為單位
  let start = 0;
  let end = fruitArray.length - 1;
  let mid;
  
  while(start <= end){
    //  從中間開始切
    mid = Math.floor( (start + end ) / 2)
    if(target < fruitArray[mid]){
	  // 往左找
      end = mid - 1;
    }else if(target > fruitArray[mid]){
	  // 往右找
      start = mid + 1
	}else{
	  return mid;
	};
 }

 // 如果上面都不符合代表找不到
 return -1;
}
// 當然用水果例子我會先用 charCodeAt 字串轉數字再進行 binarySearch

明天會來解跟 Binary Search 有關的 LeetCode 題目。

如有錯誤或需要改進的地方,拜託跟我說。
我會以最快速度修改,感謝您

上一篇
排序 4: 快速排序 Quick Sort
下一篇
[LeetCode #1064] Binary Search
系列文
前端工程師用 javaScript 學演算法32

尚未有邦友留言

立即登入留言