Aim : Implementation of recursive and non-recursive functions to perform the following searching operations for a key value in a given list of integers: i) Linear search ii) Binary search.

Theory

📌 Searching Techniques

🔹 (i) Linear Search

Linear search is a simple searching algorithm that sequentially checks each element in the list until the desired element (key) is found or the list ends.

📌 Working of Linear Search

• Start from the first element of the array.
• Compare each element with the key.
• If a match is found, return the index of the element.
• If the list ends without finding the key, return -1 (element not found).

📌 Time Complexity:

• Best Case: O(1) (Key found at the first position)
• Worst Case: O(n) (Key found at the last position or not present)
• Average Case: O(n) (Key present in the middle of the list)

🔹 (ii) Binary Search

Binary search is a more efficient searching algorithm that works on sorted arrays. It repeatedly divides the search space into halves until the key is found or the search space becomes empty.

📌 Working of Binary Search

• Find the middle element of the array.
• If the middle element is the key, return its index.
• If the key is smaller, search in the left half.
• If the key is larger, search in the right half.
• Repeat this process until the key is found or the subarray size reduces to zero.

📌 Time Complexity:

• Best Case: O(1) (Key found at the middle)
• Worst Case: O(log n) (Key found at the extreme ends)
• Average Case: O(log n) (Each step reduces the search space by half)

Search Type	Iterative (Non-Recursive)	Recursive
Linear Search	Uses a loop to check elements sequentially.	Calls itself recursively for each index.
Binary Search	Uses a loop to repeatedly divide the array.	Calls itself recursively with a new range.
Memory Usage	Lower (no extra function calls).	Higher (due to recursive function stack).
Performance	Efficient for small datasets.	More readable but uses extra memory.