Q.Write a program that takes as input a list having a mix of 10 negative and positive numbers and a key value. Apply linear search to find whether the key is present in the list or not. If the key is present it should display the position of the key in the list otherwise it should print an appropriate message. Run the program for at least 3 different keys and note the result.

Linear search is a simple algorithm for finding an element within a list. It sequentially checks each element of the list until a match is found or the entire list has been searched.

Here is a Python program that implements linear search as described, along with its execution for three different key values.

def linear_search(data_list, key):
    """
    Performs a linear search on data_list to find the key.
    
    Args:
        data_list: The list of numbers to search through.
        key: The value to search for.
        
    Returns:
        The 0-based index of the key if found, otherwise -1.
    """
    # Iterate through the list using enumerate to get both index and value
    for index, element in enumerate(data_list):
        # If the current element matches the key, return its index
        if element == key:
            return index
    # If the loop completes, the key was not found in the list
    return -1

# Define the input list with 10 mixed negative and positive numbers
my_list = [-5, 12, -3, 8, 0, 15, -10, 7, -1, 4]
print(f"The list is: {my_list}\n")

# Test cases for different keys
test_keys = [8, -5, 99]

for key_to_find in test_keys:
    print(f"Searching for key: {key_to_find}")
    # Call the linear_search function
    position = linear_search(my_list, key_to_find)

    # Display the result based on the returned position
    if position != -1:
        print(f"Key {key_to_find} found at position (0-based index): {position}")
    else:
        print(f"Key {key_to_find} not found in the list.")
    print("-" * 30)

Explanation of Key Lines:

1. def linear_search(data_list, key):: This defines a function named linear_search that takes two arguments: data_list (the list to be searched) and key (the value to find).
2. for index, element in enumerate(data_list):: This loop iterates through data_list. The enumerate() function is crucial here as it provides both the index (0-based position) and the element (value) for each item in the list during iteration.
3. if element == key:: This is the core comparison step of linear search. It checks if the current element from the list matches the key we are looking for.
4. return index: If a match is found, the function immediately returns the index where the key was located. This stops the search as soon as the first occurrence is found.
5. return -1: If the for loop completes without finding any match (i.e., the if element == key condition was never met), it means the key is not present in the list. In this case, the function returns -1 as a conventional indicator that the element was not found.
6. my_list = [-5, 12, -3, 8, 0, 15, -10, 7, -1, 4]: This line initializes the list with 10 mixed positive and negative numbers as required.
7. test_keys = [8, -5, 99]: This list holds the different key values for which the search will be performed, demonstrating various scenarios (key found, key not found).
8. if position != -1:: After calling linear_search, this conditional statement checks the returned value. If it's not -1, the key was found, and its position is printed. Otherwise, an appropriate "not found" message is displayed.

Output of the Program:

The list is: [-5, 12, -3, 8, 0, 15, -10, 7, -1, 4]

Searching for key: 8
Key 8 found at position (0-based index): 3
------------------------------
Searching for key: -5
Key -5 found at position (0-based index): 0
------------------------------
Searching for key: 99
Key 99 not found in the list.
------------------------------

Linear search is a fundamental algorithm used to find a specific element (the "key") within a list or array. It's called "linear" because it checks each element in the list sequentially, from the beginning to the end, until the key is found or the entire list has been traversed.

Why Linear Search?

Linear search is the right tool when:

1. The list is unsorted: Many other efficient search algorithms (like binary search) require the list to be sorted. Linear search works perfectly well on unsorted data.
2. The list is small: For small lists, the overhead of more complex algorithms might outweigh the benefits of their speed. Linear search is simple to implement and often fast enough for small data sets.
3. Simplicity is preferred: It's one of the easiest search algorithms to understand and code, making it a good starting point for learning about search techniques.

The core idea is to compare the key with each element of the list one by one. If a match is found, we know the key is present and its position. If we go through the entire list without finding a match, the key is not present.

Algorithm for Linear Search

Here are the steps to perform a linear search:

1. Initialization: Start searching from the first element of the list (index 0).
2. Iteration: Go through each element of the list, one by one.
3. Comparison: In each step, compare the current element with the key you are looking for.
4. Match Found: If the current element matches the key:
   • The search is successful.
   • Record the current index (position) of the element.
   • Stop the search.
5. No Match: If the current element does not match the key, move to the next element in the list.
6. End of List: If you have checked all elements in the list and no match was found:
   • The search is unsuccessful.
   • Indicate that the key is not present.

Python Program

The program defines a function linear_search that takes the list and the key as input. It iterates through the list using a for loop with range(len(data_list)) to access elements by their index. If a match is found, the index is returned immediately. If the loop completes without finding the key, it means the key is not in the list, and the function returns -1 to indicate this.

def linear_search(data_list, key):
    """
    Performs a linear search to find the key in the data_list.
    Returns the index of the key if found, otherwise returns -1.
    """
    # Iterate through the list using indices
    for i in range(len(data_list)):
        # Compare the current element with the key
        if data_list[i] == key:
            return i  # Key found at index 'i', return its position
    
    # If the loop completes, it means the key was not found in the list
    return -1

# Main part of the program execution
if __name__ == "__main__":
    # Define the list of 10 mixed negative and positive numbers
    my_list = [-5, 12, -3, 8, 0, -10, 7, -1, 4, 9]
    print(f"The list for search is: {my_list}")

    # Define a set of keys to test the program
    # We will test with a key present in the middle, a key present at the start, and a key not present.
    keys_to_test = [8, -5, 100] 

    # Run the program for each of the defined keys
    for test_key in keys_to_test:
        print(f"\n--- Searching for key: {test_key} ---")
        
        # Call the linear_search function
        position = linear_search(my_list, test_key)

        # Display the result based on the return value of linear_search
        if position != -1:
            print(f"Key {test_key} found at position (index): {position}")
        else:
            print(f"Key {test_key} not found in the list.")

Explanation of Key Lines

1. for i in range(len(data_list)):

   • This loop iterates through the indices of the data_list from 0 up to len(data_list) - 1. Using indices allows us to directly access elements and also to return the position if the key is found.

2. if data_list[i] == key:

   • This is the core comparison step. In each iteration, the element at the current index i (data_list[i]) is compared with the key we are searching for.

3. return i

   • If the key matches data_list[i], this line is executed. It immediately returns the current index i, indicating that the key has been found at this position. The function execution stops here.

4. return -1

   • This line is reached only if the for loop completes without finding any match. Returning -1 is a common convention to signal that the search was unsuccessful and the key was not found in the list.

Program Output for Different Keys

Here is the output when the program is run with the specified list [-5, 12, -3, 8, 0, -10, 7, -1, 4, 9] and the test keys 8, -5, and 100:

The list for search is: [-5, 12, -3, 8, 0, -10, 7, -1, 4, 9]

--- Searching for key: 8 ---
Key 8 found at position (index): 3

--- Searching for key: -5 ---
Key -5 found at position (index): 0

--- Searching for key: 100 ---
Key 100 not found in the list.