DSA: Searching in a Linear List: Python

Table of Contents

Algorithm for Searching in a Linear List:

Plaintext

#Initialize counter by assigning the lower bound value of the linear list

Step 1: Start
Step 2: Set ctr = L                      #L (Lower bound) is 0 (zero)
        #Now search for the ITEM

Step 3: Repeat steps 3 through 4 until ctr > U.  #U (Upper bound) is size-1
Step 4: IF AR[ctr] = = ITEM then
        {
          print("Search Successful")
          print(ctr, "is the location of", ITEM)
          break                         # go out of the loop
        }
  
Step 5: ctr = ctr + 1
        #end of repeat
        
Step 6: IF ctr > U then
            print("Search Unsuccessful !!")
                   
Step 7: Stop / End

The technique above searches for ITEM in a linear list AR with lower and upper bounds. When the search is successful, it jumps out of the loop (break statement); otherwise, it continues until the last element.

Linear Searching in an Array (Linear List)

Python

def Lsearch(AR, ITEM):
    i = 0
    while i < len(AR) and AR[i] != ITEM:
        i += 1
    if i < len(AR):
        return i
    else:
        return False

#----- main -----
N = int(input("Enter desired linear-list size (max. 50): "))
print("\nEnter elements for Linear List\n")
AR = [0] * N  # Initialize List of size N with zeros

for i in range(N):
    AR[i] = int(input("Element " + str(i) + ": "))

ITEM = int(input("Element to search: "))
index = Lsearch(AR, ITEM)

if index is not False:
    print("\nElement found at index:", index, ", Position:", (index + 1))
else:
    print("\nSorry!! Given element could not be found.\n")

The provided code performs a linear search on the list to find a specific item. Let’s go through it step-by-step to understand how it works and identify any issues.

Linear Search Function

Python

def Lsearch(AR, ITEM):
    i = 0
    while i < len(AR) and AR[i] != ITEM:
        i += 1
    if i < len(AR):
        return i
    else:
        return False

Function Definition: The function Lsearch takes two arguments: AR (the list) and ITEM (the item to be searched for).

Initialization: The variable i is initialized to 0. This variable will be used to traverse the list.

Return Statement: After the loop, if i is less than the length of AR, it means the item was found, and the function returns i. Otherwise, it returns False.

While Loop: The loop runs as long as i is less than the length of AR and AR[i] is not equal to ITEM.

If AR[i] equals ITEM, the loop stops, and the current value of i will be the index of the found item.
If the loop is completed without finding ITEM, i will be equal to the length of AR.

Main Program

Python

#----- main -----
N = int(input("Enter desired linear - list size(max.50)..."))
print("\nEnter elements for Linear List\n")
AR = [0] * N                          # Initialize List of size N with zeros

for i in range(N):
    AR[i] = int(input("Element" + str(i) + ":"))

ITEM = int(input("Element to search: "))
index = Lsearch(AR, ITEM)

if index is not False:
    print("\nElement found at index: ", index, ", Position: ", (index + 1))
else:
    print("\nSorry!! Given element could not be found.\n")

Input for List Size: The user is prompted to enter the desired size of the list N, with a maximum of 50 elements.

Initialization: A list AR of size N is set to zeros.

List Population: A loop is executed N times to populate the list AR with user-supplied elements.

Input for ITEM: The user is prompted to enter the item to look for in the list.

Calling Linear Search: The Lsearch function is called with AR and ITEM as inputs, and the result is saved in the index.

Checking Search Results:

If index is not False, it signifies the item was discovered, and the index and position (index + 1) are displayed.
If index is False, a message stating that the item was not found is printed.

Delve deeper into DSA with Lounge Coder, explore them below:

For JavaScript: Searching in a linear List

DSA: What is a Linked List?

DSA: Types of Linked Lists

DSA: Singly Linked List

DSA: Doubly Linked List