Talk:Linear search

Pseudocode implementation:

Linear search looks like the following in pseudocode:

Input is a list L and a value V. L[x] will denote the xth element in L, which consists of N values, L[1], L[2], ..., L[N].

function linear-search(L,N,V) set index = 1 repeat while index <= N if L[index] = V return success end-if set index = index + 1 end-repeat return failure end-function

Worth an article?

Does linear search (which is so simple it doesn't even deserve to be called an "algorithm") even DESERVE an article? --User:Juuitchan

Yes. It gets used and it gets called "linear search." People might not know what that is. It totally deserves a place in an encyclopedia. Graue

I agree that Linear Search deserves a Wikipedia article. However, most of the example implementations don't implement linear search, they simply call a stdlib function that (presumably) implements it. I mean, wouldn't it be silly if the examples given for the Quicksort article were all "sort array", "sort(array)", "qsort(array)"? -- Jon Harrop

Hopefully this point is moot now. --Jorge Stolfi (talk) 00:10, 22 December 2009 (UTC)

VB

Is it possible to get a VisualBasic example of a linear search posted by someone with appropriate knowledge? Thanks.

Rather not; Wikipedia is not a language tutorial, much less a tutorial for all programming languages mixed together. Any Visual basic textbook, or on-line VB tutorial, will have an example of linear search. --Jorge Stolfi (talk) 00:08, 22 December 2009 (UTC)

Removed the examples in Java and OCaml

I removed the following examples in Java and OCaml:

The following code example for the Java programming language is a simple implementation of a linear search.

 public int linearSearch(int a[], int valueToFind) {
   //a[] is an array of integers to search.
   //valueToFind is the number that will be found.
   //The function returns the position of the value if found.
   //The function returns -1 if valueToFind was not found.
   for (int i=0; i<a.length; i++) {
     if (valueToFind == a[i]) {
       return i;
     }
   }
   return -1;
 }

The List module in the OCaml standard library defines a function called "mem" that returns true if the given element is in the given list or false if not. This function could be defined as:

let rec mem x = function
    [] -> false
  | h :: t -> h=x || mem x t

These examples do not add any information about the linear search algorithm besides what is already given by the pseudocode; and is useless to readers who are not Java or OCaml programmers.

Removed Mathematica example

I removed the following texts:

Mathematica's unusually powerful pattern matching allows linear search to be implemented by a pattern match:

Mem[x_, {___, x_, ___}] := True Mem[_, _] := False

This example does not explain what linear search is, since it does not show how Mathematica performs the pattern matching. Besides, the example is useless for readers who are not expert Mathematica users.

Incorrect Recursive Pseudocode?

How can the location of the desired value be returned? The location of the found item will always be the first location. 70.42.240.5 (talk) 16:45, 30 January 2014 (UTC)

The code is fine. The recursion walks down the list; the locations of the items do not change, so returning the location (which is the first element of a SUBlist and not necessarily the list itself) is the right value. Glrx (talk) 20:20, 1 February 2014 (UTC)

Application

" .. in practice even on medium sized arrays (around 100 items or less) it might be infeasible to use anything else. On larger arrays, it only makes sense to use other, faster search methods if the data is large enough, because the initial time to prepare (sort) the data is comparable to many linear searches"

Since 3 < 100, is an array with 3 elements of "medium size". What was the writer trying to say by "if the data is large enough" - apparently "on larger arrays"? — Preceding unsigned comment added by 75.79.3.184 (talk • contribs) 03:34, 20 May 2014

It means that,

1. In theory, if the array size grows beyond a "small" size, binary search and other more advanced search methods are faster than just brute forcing with linear search. The cited source says that in practice there are plenty of cases where linear search is faster (hence even on "medium" size).

2. For large arrays, on the other hand, binary search, etc. may indeed be faster, but it requires data preparation (binary search requires a sorted list). So one needs to ask if the benefits of running a faster search method outweighs the extra time and effort of sorting the list first. You would need to conduct enough searches on the same list for that time to be worth it, and the advantage decreases if the list keeps changing. 2603:8000:B600:4000:2CA5:C8BE:9CAD:F1D1 (talk) 02:12, 15 September 2022 (UTC)

This section makes no sense. It does make some sense if you ignore the second paragraph "When many values..."

I conclude that someone has inserted the second paragraph later, without properly reading the existing text. — Preceding unsigned comment added by 80.47.212.205 (talk) 19:28, 12 November 2023 (UTC)

Remove Duplicate definition and Updated

1.) I would like to suggest that what appears to be a duplicate definition be removed The article appears to be repeating the same definition in multiple locations. The first instance is the first sentence "linear search or sequential search is a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched". The second occurrence is found in the section labeled Algorithm where it appears to repeat nearly repeats the same verbiage, "Linear search sequentially checks each element of the list until it finds an element that matches the target value. If the algorithm reaches the end of the list, the search terminates unsuccessfully."

PROPOSED SOLUTION: Would a section labeled *Definition* where all areas of the article can reference it rather than having multiple, slightly different definitions, be appropriate?  

2.) Does the result of not finding a value in a list constitute an "unsuccessful" search? If you accept that the purpose of any search algorithm is to determine if an item resides within a set of elements then not finding a specific item is not an unsuccessful search at all. The search has successfully proven that the item is, in fact, is not in the list.

PROPOSED SOLUTION: Remove the last part of the sentence describing the search as unsuccessful.  — Preceding unsigned comment added by Dirkste (talk • contribs) 18:34, 6 December 2017 (UTC)