搜尋演算法

搜尋演算法就是在狀態空間進行枚舉，通過某種方式（可能是枚舉、或一些啟發是策略）來計算符合特定條件的解或最佳解。

常見的搜尋演算法

• 線性搜尋：線性搜尋是最基本的搜尋方法，它通過按順序檢查每個元素來查找特定值。
• 二分搜尋：二分搜尋是一種高效的搜尋方法，它在排序的數據集中工作，通過不斷地將搜尋範圍縮小一半來查找特定值。

  ool search(int x[], int n, int k) {
  int l = 0, r = n-1;
  while (l <= r) {
  	int m = (l+r)/2;
  	if (x[m] == k) return true;
  	if (x[m] < k) l = m+1; else r = m-1;
  }
  return false;
  
  ``
  

• 雜湊表搜尋（Hashing）：雜湊搜尋通過使用雜湊函數將目標值映射到索引上，然後直接訪問該索引以查找目標值。

搜尋演算法的常見應用

搜尋演算法通常用於解決範圍查詢、子序列問題、以及其他需要在數據集或狀態空間中查找特定元素的問題。

例如，在二分搜的應用上，可以參考 Topcoder 的教學，它解釋了如何使用 C++ 的 Standard Template Library 來實現二分搜尋，並提供了不同的二分搜尋方法，例如 lower_bound、upper_bound、binary_search 和 equal_range