Linear Search

The Idea of Linear Search

Linear search is the simplest way to find an item in a list. It works by checking every single element, one after another, from the very first element to the last. Because it goes through the list in order, it is also called sequential search or serial search.

The element you are looking for is called the key. The search compares the key with each element of the list. If a match is found, the search is successful and stops. If the entire list is checked and no match is found, the search is unsuccessful — the key is not present.

This method is best suited for small collections of data or for lists that are unordered (not sorted). It does not require the list to be arranged in any particular order.

---

How the Algorithm Works

The algorithm takes three inputs: the list (numList), the key to search for (key), and the number of elements in the list (n).

1. Start with index = 0 (the first position).
2. While index is less than n, do the following:
   • Check if the element at numList[index] equals the key.
   • If yes, print the position (which is index + 1, because list indices start at 0) and stop.
   • If no, increase index by 1 and repeat.
3. If the loop finishes without finding the key, print "Search unsuccessful".

Algorithm 6.1: Linear Search

Given a list numList of n elements and a key value K, this is the book's own step-by-step algorithm for finding the position of the key in numList:

LinearSearch(numList, key, n)
Step 1: SET index = 0
Step 2: WHILE index < n, REPEAT Step 3
Step 3: IF numlist[index]= key THEN
                PRINT "Element found at position", index+1
        STOP
    ELSE
                index = index+1
Step 4: PRINT "Search unsuccessful"

---

Step-by-Step Example

Consider a list with seven elements: [8, -4, 7, 17, 0, 2, 19]. The indices are:

Suppose we search for key = 17. The algorithm proceeds as follows:

• index = 0: Is 0 < 7? Yes. Is 8 = 17? No. Move to index 1.
• index = 1: Is 1 < 7? Yes. Is -4 = 17? No. Move to index 2.
• index = 2: Is 2 < 7? Yes. Is 7 = 17? No. Move to index 3.
• index = 3: Is 3 < 7? Yes. Is 17 = 17? Yes. Element found at position 4.

The search made 4 comparisons and stopped.

---

Best Case, Worst Case, and Key Observations

Best case: The key is the very first element in the list. Only 1 comparison is needed. For example, if the list were [17, 8, -4, 7, 0, 2, 19] and we search for 17, the algorithm finds it at index 0 in one step.

Worst case: The key is the last element in the list, or the key is not present at all. In both situations, the algorithm must compare every single element. This requires n comparisons (where n is the total number of elements). For example, if the list is [8, -4, 7, 0, 2, 19, 17] and we search for 17, it takes 7 comparisons. Similarly, searching for a key like 10 (which is not in the list) also takes 7 comparisons.

---

The Python Program

Program 6-1: Linear Search

def linearSearch(list, key):        #function to perform the search
    for index in range(0,len(list)):
        if list[index] == key:      #key is present
            return index+1          #position of key in list
    return None  #key is not in list
#end of function

list1 = []   #Create an empty list
maximum = int(input("How many elements in your list? "))
print("Enter each element and press enter: ")
for i in range(0,maximum):
    n = int(input())
    list1.append(n)     #append elements to the list
print("The List contents are:", list1)

key = int(input("Enter the number to be searched:"))
position = linearSearch(list1, key)
if position is None:
    print("Number",key,"is not present in the list")
else:
    print("Number",key,"is present at position",position)

The textbook provides a complete Python function for linear search. Here is how it works:

• The function linearSearch(list, key) takes a list and the key as input.
• It uses a for loop with range(0, len(list)) to go through each index.
• If list[index] == key, it returns index + 1 (the position as humans count it).
• If the loop finishes without finding the key, it returns None.
• The main program asks the user for the number of elements, then each element, and finally the key to search. It calls the function and prints the result. …