Instruction

Code for Linear Search

Python

Code for the load_strings function should be added following the load_numbers function in the load.py file:

def load_numbers(file_name):
  numbers = []
  with open(file_name) as f:
    for line in f:
      numbers.append(int(line))
  return numbers

def load_strings(file_name):
  strings = []
  with open(file_name) as f:
    for line in f:
      strings.append(line.rstrip())
  return strings

Save the following code in a file named linear_search.py:

# As usual, this code at the top isn't relevant to the search
# algorithm. It's just like the code that loaded a list of numbers
# from a file in the previous stage, but this code calls a the above
# function, load_strings, to load a list of strings in.
import sys
from load import load_strings

names = load_strings(sys.argv[1])

# Here's a separate hard-coded list containing the 100 names we're
# going to search for. We'll loop through each name in the list, and
# pass it to our search function to get the index within the full
# list where it appears.
search_names = ["Francina Vigneault", "Lucie Hansman", "Nancie Rubalcaba", "Elida Sleight", "Guy Lashbaugh", "Ginger Schlossman", "Suellen Luaces", "Jamey Kirchgesler", "Amiee Elwer", "Lacresha Peet", "Leonia Goretti", "Carina Bunge", "Renee Brendeland", "Andrew Mcgibney", "Gina Degon", "Deandra Pihl", "Desmond Steindorf", "Magda Growney", "Tawana Srivastava", "Tammi Todman", "Harley Mussell", "Iola Bordenet", "Edwardo Khela", "Myles Deanne", "Elden Dohrman", "Ira Hooghkirk", "Eileen Stigers", "Mariann Melena", "Maryrose Badura", "Ardelia Koffler", "Lacresha Kempker", "Charlyn Singley", "Lekisha Tawney", "Christena Botras", "Mike Blanchet", "Cathryn Hinkson", "Errol Shinkle", "Mavis Bhardwaj", "Sung Filipi", "Keiko Dedeke", "Lorelei Morrical", "Jimmie Lessin", "Adrianne Hercules", "Latrisha Haen", "Denny Friedeck", "Emmett Whitesell", "Sina Sauby", "Melony Engwer", "Alina Reichel", "Rosamond Shawe", "Elinore Benyard", "Sang Bouy", "Ed Aparo", "Sheri Wedding", "Sang Snellgrove", "Shaquana Sones", "Elvia Motamed", "Candice Lucey", "Sibyl Froeschle", "Ray Spratling", "Cody Mandeville", "Donita Cheatham", "Darren Later", "Johnnie Stivanson", "Enola Kohli", "Leann Muccia", "Carey Philps", "Suellen Tohonnie", "Evelynn Delucia", "Luz Kliment", "Lettie Jirjis", "Francene Klebe", "Margart Scholz", "Sarah Growden", "Glennis Gines", "Rachael Ojima", "Teofila Stample", "Narcisa Shanley", "Gene Lesnick", "Malena Applebaum", "Norma Tingey", "Marianela Mcmullen", "Rosalva Dosreis", "Dallas Heinzmann", "Sade Streitnatter", "Lea Pelzel", "Judith Zwahlen", "Hope Vacarro", "Annette Ayudan", "Irvin Cyree", "Scottie Levenstein", "Agustina Kobel", "Kira Moala", "Fawn Englar", "Jamal Gillians", "Karen Lauterborn", "Kit Karratti", "Steven Deras", "Mary Rosenberger", "Alonso Viviano"]

# Now let's implement the search function. Compared to the sorting
# algorithms, this is going to be short. The index_of_item function
# takes the Python list you want to search through, and a single
# target value you want to search for.
def index_of_item(collection, target):
  # Now we need to loop over each item in the list. The range
  # function gives us a range of numbers from its first argument up
  # to, but not including, its second argument. So if our list had a
  # length of five, this would loop over the indexes 0 through 4.
  for i in range(0, len(collection)):
    # We test whether the list item at the current index matches our
    # target.
    if target == collection[i]:
      # If it does, then we return the index of the current
      # item. This will exit the index_of_item function without
      # looping over the remaining items in the list.
      return i
  # If we reach the end of the loop without finding the target value,
  # that means it wasn't in the list. So instead of returning an
  # index, we return the special Python value "None", which indicates
  # the absence of a value.  Other languages have similar values like
  # "nil" or "null", but if yours doesn't, you might have to return a
  # value that would otherwise be impossible, like an index of "-1".
  return None

# Now let's call our new search function. We start by looping over
# the list of 100 values we're looking for. We're using the values
# themselves this time, not their indexes within the list, so there's
# no need to mess with Python's "range" function.
for n in search_names:
  # Here's the actual call to the index_of_item function. We pass it
  # the full list of names that we loaded from the file, plus the
  # name we want to search for within that list. Then we store the
  # index it returns in a variable.
  index = index_of_item(names, n)
  # Lastly, we print the index we got back.
  print(index)

You can retrieve the unsorted.txt file by launching the Workspace associated with the preceding video and choosing the download option from the File menu. Save it under a subdirectory named names.

To run this code:

python linear_search.py names/unsorted.txt

JavaScript

function indexOfItem(collection, target) {
    for (var i = 0; i < collection.length; i++) {
        if (collection[i] === target) {
            return i;
        }
    }
    return null;
}

const names = ["Francina Vigneault", "Lucie Hansman", "Nancie Rubalcaba", "Elida Sleight"];

var index = indexOfItem(names, "Lucie Hansman");
console.log(index); // prints: 1

Java

import java.util.*;

public class Search {
    static int indexOfItem(List<String> list, String target) {
        int length = list.size();
        for (int i = 0; i < length; i++) {
            if (list.get(i).equals(target)) {
                return i;
            }
        }
        // We have to return an integer, so return an "impossible"
        // index to indicate value was not found.
        return -1;
    }

    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<String>(
            Arrays.asList("Francina Vigneault", "Lucie Hansman", "Nancie Rubalcaba", "Elida Sleight"));
        System.out.println(indexOfItem(list, "Lucie Hansman"));
    }
}

C-Sharp

using System;
using System.Collections.Generic;
using System.Linq;

namespace LinearSearch
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            //var numbers = new [] { 1, 2, 3, 4, 5, 6 };
            var numbers = Enumerable.Range(1, 10000).ToArray();

            foreach (var number in numbers)
            {
                //int? result = LinearSearch(numbers, number);
                int? result = GenericLinearSearch(numbers, number);

                if (result != null && result == (number - 1))
                {
                    Console.WriteLine($"Index for '{number}' is '{result}'");
                }
                else
                {
                    throw new Exception("Oh no!");
                }
            }

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

Algorithms: Sorting and Searching

Code for Linear Search

Python

JavaScript

Java

C-Sharp