[用JS來寫演算法和了解資料結構] Day10 Algorithm - Searching / Traversal

Searching / Traversal

Search
簡易搜尋/線性搜索 Sequential Search/Linear Search - O(n)
二分搜尋 Binary Search - O(log n)

Traversal
Depth First Search (DFS) 先 上到下 再 左到右 - O(n)
Breadth First Search (BFS) 先 左到右 再 上到下 - O(n)

• DFS use lower memories than BFS

簡易搜尋/線性搜索 Sequential Search/Linear Search

Time - O(n)

1個耗費的步驟1次O(1) ，n個耗費的步驟就是n次O(n)，

• 把array中所有的數值都列出來
• 從一個沒有順序的array中找出某個元素，不知道index的情況下

function findNum(ary, target){
  for(let i = 0; i < ary.length; i++){
	  if(ary[i] === target){
	  	return true
	  }
  }
  return false
}

findNum([1,5,6,7,2], 2);

以下 array內建的搜尋法都是 Linear Search looping 一遍 O(n)

const beasts = ["Centaur", "Godzilla", "Minotaur", "Hydra"];

beasts.indexOf("Godzilla"); // 回傳 1 找到的index 找不到 -1

beasts.findIndex((item) => {  
    return item === "Godzilla";
});
// 回傳 1 找到的index 找不到 -1

beasts.find((item) => {      
    return item === "Godzilla";
});
// 回傳 "Godzilla" 找到的item  找不到 undefined

beasts.includes("Godzilla");
//true or false

• 在一個沒有順序的array中找出最大或最小值

function findMax(ary) {
  let max;
  for (let i = 0; i < ary.length; i++) {
    if(max === undefined || max < ary[i]) {
      max = ary[i];
    }
  }
  return max;
}

findMax([1,5,6,7,2]);

找第二大

function findSecondMax(ary) {
  let max, second;
  for (let i = 0; i < ary.length; i++) {
    if(max === undefined || max < ary[i]) {
      second = max;
      max = ary[i];
    }else if(second === undefined || second < ary[i]){
      second = ary[i];
    }
  }
  return second;
}

findSecondMax([1,5,6,7,2]); // 6

二分搜尋 Binary Search

Time - O(log n)

1個耗費的步驟1次O(1)，4個耗費的步驟為2次，n個耗費的步驟是log n次。

• 需注意使用二分搜尋時，必須是一個排序好陣列(例如:A-Z，1-100，小到大，大到小)。
  在生活中最熟悉的例子就是終極密碼這個遊戲，小時候可能都有玩過。1-100猜一個數字，一開始大家都會先對半切 猜50，比50大還是比50小，知道比50小後再對半猜25，接下來以此類推。恩沒錯…這個就是二分搜尋的概念。

// input ary = [5,17,33,41,55,61,80] and target = 55
// output index 4 
function binarySearch(ary, target){
  let left = 0;
  let right = ary.length - 1; 
  let mid; 

  while(left <= right){  
    mid = Math.floor((left + right) / 2); 
    if(target === ary[mid]){   
      return mid;
    } else if(target < ary[mid]){
      right = mid - 1; 
    } else{
      left = mid + 1;   
    }
  }
  return -1;
}

binarySearch([5,17,33,41,55,61,80], 55);

Traversal

• Breadth First Search (BFS) 先 左到右 再 上到下 - O(n)

Pro:
Shortest Path
Closer Nodes

Con:
More Memory

• Depth First Search (DFS) 先 上到下 再 左到右 - O(n)

Pro:
Less Memory
Does Path Exit?

Con:
Can Get Slow

Interview question

• If you know a solution is not far from the root of the tree:
  BFS

• If the tree is very deep and solutions are rare:
  BFS - DFS will be slower

• If the tree is very wide:
  DFS - BFS will need too much memory, in a queue

• If solutions are frequent but located deep in the tree:
  DFS

• Determining whether a path exists between two nodes:
  DFS

• Finding the shortest path:
  BFS

學習與參考資料

• Master the Coding Interview: Data Structures + Algorithms