線形探索の説明

線形検索とは何ですか?

リストまたはアイテムの配列が与えられたとします。あなたは特定のアイテムを探しています。どうやってそれをしますか?

与えられたリストで番号13を見つけます。

線形探索1

リストを見るだけで、そこにあります!

線形探索2

さて、どのようにコンピュータにそれを見つけるように伝えますか?

コンピューターは、特定の時点で値を超える値を確認することはできません。したがって、配列から1つの項目を取得し、それが探しているものと同じであるかどうかを確認します。

線形探索3

最初の項目が一致しませんでした。だから次のものに移動します。

線形探索4

等々…

これは、一致するものが見つかるまで、またはすべての項目がチェックされるまで行われます。

線形探索5

このアルゴリズムでは、アイテムが見つかったときに停止でき、それ以上調べる必要はありません。

では、線形探索操作を行うのにどのくらい時間がかかりますか?最良の場合、あなたは幸運になる可能性があり、あなたが見ているアイテムはおそらく配列の最初の位置にあります!

ただし、最悪の場合、最後の場所でアイテムを見つける前、またはアイテムが配列にないことに気付く前に、すべてのアイテムを確認する必要があります。

したがって、線形探索の複雑さはO(n)です。

検索対象の要素が最初のメモリブロックに存在する場合、複雑さはO(1)になります。

JavaScriptの線形検索関数のコードを以下に示します。この関数は、配列内で探しているアイテムの位置を返します。項目が配列に存在しない場合、関数はnullを返します。

Javascriptの例

function linearSearch(arr, item) { // Go through all the elements of arr to look for item. for (var i = 0; i < arr.length; i++) { if (arr[i] === item) { // Found it! return i; } } // Item not found in the array. return null; }

Rubyでの例

def linear_search(target, array) counter = 0 while counter < array.length if array[counter] == target return counter else counter += 1 end end return nil end

C ++での例

int linear_search(int arr[],int n,int num) { for(int i=0;i

Example in Python

def linear_search(array, num): for i in range(len(array)): if (array[i]==num): return i return -1

Global Linear Search

What if you are searching the multiple occurrences of an element? For example you want to see how many 5’s are in an array.

Target = 5

Array = [ 1, 2, 3, 4, 5, 6, 5, 7, 8, 9, 5]

This array has 3 occurrences of 5s and we want to return the indexes (where they are in the array) of all of them.

This is called global linear search and you will need to adjust your code to return an array of the index points at which it finds your target element.

When you find an index element that matches your target, the index point (counter) will be added in the results array. If it doesn’t match, the code will continue to move on to the next element in the array by adding 1 to the counter.

def global_linear_search(target, array) counter = 0 results = [] while counter < array.length if array[counter] == target results << counter counter += 1 else counter += 1 end end if results.empty? return nil else return results end end

Why linear search is not efficient

There is no doubt that linear search is simple. But because it compares each element one by one, it is time consuming and therefore not very efficient. If we have to find a number from, say, 1,000,000 numbers and that number is at the last position, a linear search technique would become quite tedious.

So you should also learn about bubble sort, quick sort and other more efficient algorithms.

Other search algorithms:

  • How to implement quick sort
  • Binary search algorithm
  • Jump search algorithm
  • Search algorithms explained with examples
  • Implement a binary search algorithm in Java without recursion
  • More info on search algorithms

Original text