Pencarian Linear Dijelaskan

Apa itu Carian Linear?

Katakan anda diberi senarai atau pelbagai item. Anda sedang mencari item tertentu. Bagaimana anda melakukannya?

Cari nombor 13 dalam senarai yang diberikan.

Carian Linear 1

Anda hanya melihat senarai dan ada!

Pencarian Linear 2

Sekarang, bagaimana anda memberitahu komputer untuk mencarinya?

Komputer tidak dapat melihat lebih dari sekadar nilai pada waktu tertentu. Oleh itu, ia mengambil satu item dari array dan memeriksa sama seperti item yang anda cari.

Pencarian Linear 3

Item pertama tidak sepadan. Oleh itu, beralih ke yang seterusnya.

Carian Linear 4

Dan sebagainya…

Ini dilakukan sehingga perlawanan dijumpai atau sehingga semua item telah diperiksa.

Carian Linear 5

Dalam algoritma ini, anda boleh berhenti apabila item tersebut dijumpai dan tidak perlu melihat lebih jauh.

Jadi berapa lama masa yang diperlukan untuk melakukan operasi carian linear? Dalam kes terbaik, anda mungkin bernasib baik dan item yang anda cari mungkin berada di kedudukan pertama dalam barisan!

Tetapi dalam keadaan terburuk, anda harus melihat setiap item sebelum anda menemui item tersebut di tempat terakhir atau sebelum anda menyedari bahawa item tersebut tidak terdapat dalam larik.

Oleh itu, kerumitan carian linear adalah O (n).

Sekiranya elemen yang hendak dicari tinggal di blok memori pertama maka kerumitannya adalah: O (1).

Kod untuk fungsi carian linear dalam JavaScript ditunjukkan di bawah. Fungsi ini mengembalikan kedudukan item yang kita cari dalam tatasusunan. Sekiranya item tidak terdapat dalam larik, fungsi akan kembali nol.

Contoh dalam 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; }

Contoh dalam 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

Contoh dalam 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