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
}