Instruction

# Linear Search Implementations

## Python

The implementation of linear search covered in the course is provided below.

```def linear_search(lst, target):
"""Returns the index position of the target if found, else returns -1"""

for i in range(0, len(lst)):
if lst[i] == target:
return i
return -1
```

The code can be cleaned up a bit by using the `enumerate` function on the list.

```def linear_search(lst, target):
for index, value in enumerate(lst):
if value == target:
return index
return -1
```

## JavaScript

```function linearSearch(array, key){
for(let i = 0; i < array.length; i++){
if(array[i] === key) {
return i;
}
}
return -1;
}
```

## C#

```public class SearchExamples
{
public static int LinearSearch(int[] data, int key)
{
for (int index = 0; index < data.Length; index++)
{
if (data[index] == key)
{
return index;
}
}

return -1;
}

public static int GenericLinearSearch<T>(T[] data, T key)
{
for (int index = 0; index < data.Length; index++)
{
if (EqualityComparer<T>.Default.Equals(data[index], key))
{
return index;
}
}

return -1;
}
}
```

## Swift

Let's start with a simple implementation where we assume the array contains values of type `Int`.

```func linearSearch(_ array: [Int], target: Int) -> Int? {
for (index, value) in array.enumerated() where value == target {
return index
}

return nil
}
```

Here we've used the enumerate method on the array to iterate over both the index position in the array and the corresponding value stored at the index as a tuple.

In addition a conditional where clause is used on the for loop to only evaluate the body if the value matches the target.

```let numbers = [1,2,3,4,5,6]
linearSearch(numbers, target: 4)
```

This works as expected. We can however, make this solution generic so that we can use it on any array and not just an array of integers.

```func linearSearch<T: Equatable>(_ array: [T], target: T) -> Int? {
for (index, value) in array.enumerated() where value == target {
return index
}

return nil
}
```

The body of the function is the same, we've just introduced a generic type parameter with a constraint that it must conform to the `Equatable` protocol. The type parameter is used to restrict the target type to the same type as the array contents.

```let greetings = ["Hello", "Bonjour", "Namaste"]
linearSearch(greetings, target: "Bonjour")
```

Here we've used the function on an array of type `String` and it works as expected.

While this is a much more flexible solution it is still a global function which is rarely used in Swift. Instead a more ideal approach would be to extend the `Array` type and define linear search as a method.

```extension Array where Element: Equatable {
func linearSearch(target: Element) -> Int? {
for (index, value) in self.enumerated() where value == target {
return index
}

return nil
}
}
```

Again the body of the function is the same. Like the generic type parameter here we've constrained the generic type on `Array`, `Element`, to conform to `Equatable`. Since we don't have to pass in the array as an argument, we can call `enumerated()` on `self` to refer to the array.

We can use this method on an array of any type as long as the target is the same type as the array contents.

```numbers.linearSearch(target: 2)
greetings.linearSearch(target: "Hello")
```

The `contains(:)` method on `Collection` is implemented using linear search. Unlike linear search hower, `contains(:)` returns either `True` or `False` to indicate presence of the element in the data set.

## Java

```public class LinearSearchExample {
public static int linearSearch(int[] data, int key) {
for(int index = 0; index < data.length; index++) {
if (data[index] == key) {
return index;
}
}

return -1;
}
}
```

## PHP

```<?php
function linearSearch(Array \$list, \$key)
{
\$count = count(\$list);

for (\$i = 0; \$i < \$count; \$i++;) {
if (\$list[\$i] == \$key) {
return \$i;
}
}

return -1;
}
?>
```

## Golang

```func linearsearch(data []int, key int) bool {
for idx, item := range data {
if item == key {
return idx
}
}
return nil
}
```