線性搜尋(Linear Search)演算法，最基本的搜尋演算法

線性搜尋(Linear Search)演算法又稱為循序搜尋(Sequential Search)演算法，是學習程式語言最先需要學會的搜尋演算法。它可以按照元素在集合中的順序，從頭開始進行走訪，並連續判斷目前走訪到的元素是否是我們想要找的元素。

線性搜尋法(Linear Search)

線性搜尋法的概念

線性搜尋法是以土法煉鋼的方式走訪集合中的每個元素，並在每次迭代時去判斷目前走訪到的元素是否正是我們想要找的元素。

線性搜尋法在任何場合下都可以使用，不需要去在乎集合中的元素順序。然而雖然它直覺又方便，但它通常不會是一個很有效率的搜尋方法。

線性搜尋法的過程

前面有提到線性搜尋法可以用在任何場合，這邊就以無排序的整數陣列來舉例吧！假設現在有個整數陣列，內容如下：

索引    0   1   2   3   4   5   6   7   8
數值    9   8   3   3   9   2   4   6   3

若要用線性搜尋法來找到元素6，那就從陣列的索引0開始，判斷索引0的元素是否是6，如果不是的話就繼續判斷下一個索引的元素值。直到找到我們要找的元素值，也就是6後才停止。如果已經走訪到陣列結尾了，卻都沒有發現元素值6的話，表示6並不存在於這個陣列之中。

       ●
索引    0   1   2   3   4   5   6   7   8
數值    9   8   3   3   9   2   4   6   3
     6 != 9

           ●
索引    0   1   2   3   4   5   6   7   8
數值    9   8   3   3   9   2   4   6   3
         6 != 8

               ●
索引    0   1   2   3   4   5   6   7   8
數值    9   8   3   3   9   2   4   6   3
             6 != 3

                   ●
索引    0   1   2   3   4   5   6   7   8
數值    9   8   3   3   9   2   4   6   3
                 6 != 3

                       ●
索引    0   1   2   3   4   5   6   7   8
數值    9   8   3   3   9   2   4   6   3
                     6 != 9

                           ●
索引    0   1   2   3   4   5   6   7   8
數值    9   8   3   3   9   2   4   6   3
                         6 != 2

                               ●
索引    0   1   2   3   4   5   6   7   8
數值    9   8   3   3   9   2   4   6   3
                             6 != 4

                                   ●
索引    0   1   2   3   4   5   6   7   8
數值    9   8   3   3   9   2   4   6   3
                                 6 == 6

線性搜尋法的程式實作

/// 線性搜尋法，使用For迭代器迴圈來迭代。
pub fn linear_search(array: &[i32], target_element: i32) -> Option<usize> {
    for (index, element) in array.iter().copied().enumerate() {
        if target_element == element {
            return Some(index);
        }
    }

    None
}

/// 線性搜尋法，使用迭代器。
pub fn linear_search(array: &[i32], target_element: i32) -> Option<usize> {
    array.iter().position(|&element| element == target_element)
}

/**
 * 線性搜尋法，使用迴圈來迭代。
 */
public static int linearSearch(final int[] array, final int targetElement) {
    for (int index = 0; index < array.length; ++index) {
        if (targetElement == array[index]) {
            return index;
        }
    }

    return -1;
}

/**
 * 線性搜尋法，使用迴圈來迭代。
 */
function linearSearch(array: number[], targetElement: number) {
    for (let index = 0;index < array.length;index++) {
        if (targetElement === array[index]) {
            return index;
        }
    }

    return -1;
}

/**
 * 線性搜尋法，使用迭代器。
 */
function linearSearch(array: number[], targetElement: number) {
    return array.findIndex((element) => element === targetElement);
}

// 線性搜尋法，使用For迭代器迴圈來迭代。
func LinearSearch(array []int, targetElement int) int {
	for index, element := range array {
		if targetElement == element {
			return index
		}
	}

	return -1
}

線性搜尋法的複雜度