iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 30
0

前言

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

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

循序搜尋法 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;
}

上一篇
[Data Structure][Sort] - Quick Sort
系列文
學習資料結構30天30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言