Searching

6.1 INTRODUCTION

In our daily lives, we often store various items at home and retrieve them when needed. Sometimes, we remember the exact location of an item, making retrieval straightforward. However, other times we do not remember the exact location and need to search for the required item. Similarly, computers store vast amounts of data that need to be retrieved efficiently when demanded by a user or a program. Searching, in computer science, refers to the process of locating a particular element, called the key, within a collection of elements. The result of a search operation determines whether the key is present in the collection and, if present, its position within the collection. Searching is a fundamental technique in computer science, essential for designing efficient algorithms and data retrieval methods. Programmers must understand various searching techniques to optimize data access and manipulation.

• Searching means locating a particular element (key) in a collection.
• Search results indicate presence or absence of the key and its position if found.
• Computers store large data collections requiring efficient search techniques.
• Understanding searching is essential for designing effective algorithms.
• Searching can be straightforward if the location is known, else requires systematic methods.
• The chapter introduces three primary searching techniques: Linear Search, Binary Search, and Search by Hashing.
• 📌 Searching: Process of locating a particular element in a collection.
• 📌 Key: The element to be searched within a collection.

6.2 LINEAR SEARCH

Linear Search, also known as sequential or serial search, is the simplest and most fundamental searching technique. It involves checking each element of a list sequentially, starting from the first element and moving towards the last, comparing each element with the key until a match is found or the entire list is traversed. If the key is found, the search is successful, and the position of the key is returned. If the key is not found after checking all elements, the search is unsuccessful. Linear search is exhaustive and does not require the list to be sorted, making it suitable for small or unordered collections. However, it can be inefficient for large lists as it may require checking every element. The algorithm initializes an index at 0 and compares the element at this index with the key. If they match, the search ends. Otherwise, the index is incremented, and the process repeats until the key is found or the list ends. The worst-case scenario occurs when the key is the last element or not present at all, requiring n comparisons for a list of n elements. The best case is when the key is the first element, requiring only one comparison. **Table on page 2 (2×8)** | Index in numList | 0 | 1 | 2 | 3 | 4 | 5 | 6 | | --- | --- | --- | --- | --- | --- | --- | --- | | Value | 8 | -4 | 7 | 17 | 0 | 2 | 19 | **Table on page 3 (5×4)** | index | index < n | numList[index] = key | index=index+1 | | --- | --- | --- | --- | | 0 | 0 < 7 ? Yes | 8 = 17? No | 1 | | 1 | 1 < 7 ? Yes | -4 = 17? No | 2 | | 2 | 2 < 7 ? Yes | 7 = 17? No | 3 | | 3 | 3 < 7 ? Yes | 17 = 17? Yes | | **Table on page 3 (2×8)** | Index in numList | 0 | 1 | 2 | 3 | 4 | 5 | 6 | | --- | --- | --- | --- | --- | --- | --- | --- | | Value | 17 | 8 | -4 | 7 | 0 | 2 | 19 | **Table on page 3 (2×4)** | index | index < n | numList[index] = key | index=index+1 | | --- | --- | --- | --- | | 0 | 0 < 7 ? Yes | 17 = 17? Yes | 1 | **Table on page 16 (12×3)** | hash index = length of key - 1 | List of Keys | List of Values | | --- | --- | --- | | 0 | None | None | | 1 | UK | London | | 2 | None | None | | 3 | Cuba | Havana | | 4 | India | New Delhi | | 5 | France | Paris | | 6 | None | None | | 7 | None | None | | 8 | Australia | Canberra | | 9 | None | None | | 10 | Switzerland | Berne |

• Linear search compares each element sequentially with the key.
• It works on unordered lists and is simple to implement.
• Best case: key is first element (1 comparison).
• Worst case: key is last element or absent (n comparisons).
• Useful for small datasets due to its simplicity.
• Algorithm stops immediately when key is found.
• 📌 Linear Search: A search technique that checks each element one by one.
• 📌 Key: The element to be searched in the list.