前言

前面介紹了幾種資料的排序方式，那今天來講如何搜尋所需要的資料吧。

找資料最簡單的方法，就是一筆一筆資料慢慢找，直到找到要的那筆資料。
那就先介紹最直覺的循序搜尋吧。

循序搜尋法 Sequential Search

• 說明 :
  從陣列第1個元素搜尋到最後一個元素，找到要搜尋的值(target)就會回傳在array裡的index，
  如果target不在array裡面，就回傳-1。

• 使用對象 : 未排序的數列、Linked List

• 時間複雜度 : O(n)，Best case : O(1)。

• 程式範例 :

public static int SequentialSearch(int ary[], int target)
{
	// 遍歷要搜尋的陣列元素
	for (int index = 0; index < ary.length; i++) {
		// 若值 = 目標數值
		if (ary[index] == target) {
			// 回傳target所在的鍵值
			return index;
		}
	}

	// 目標數值 不存在於 陣列 中
	return -1;
}

接著，我們介紹二元搜尋法。

二元搜尋法 Binary Search

在有序數列中，選取中間的元素 (middle) 和目標數值(target)比較，會有三種狀況:

1. target = ary[middle]，找到target
2. target > ary[middle]，target位於數列左邊
3. target < ary[middle]，target位於數列右邊

如果是 狀況2和狀況3，就在新範圍重選一個中間值與target比較，直到搜尋到target值。

• 使用對象 : 有序數列
• 時間複雜度 : O(log n)，Best case : O(1)。
• 程式範例 :

public static int BinarySearch(int ary[], int target)
{
	// 搜尋範圍左邊界的鍵值
	int left = 0;
	// 搜尋範圍右邊界的鍵值
	int right = ary.length - 1;
	// 搜尋範圍中間的鍵值
	int middle;
	
	while (left <= right)
	{
		// 取得陣列中間的鍵值
		middle = (left + right) / 2;
		
		// 狀況1. 目標數值 = 陣列中間值
		if (target == ary[middle]) {
			return middle;
		}
		
		// 狀況2. 目標數值 存在於陣列的右半邊
		if (target > ary[middle]) {
			// 更新 left 的邊界值
			left = middle + 1;
		} else {
			// 狀況3. 目標數值 存在於陣列的左半邊
			// 更新 right 的邊界值
			right = middle - 1; 
		}
	}
	
	// 目標數值 不存在於 陣列 中
	return -1;
}