Searching is the process of locating a particular element (referred to as the key ) within a collection of elements. The search result determines whether the element is present or absent, and if present, identifies its position in the collection. Searching is a fundamental operation in computer science, critical for efficient data retrieval and algorithm design.
Linear Search (also known as sequential search or serial search) is the most fundamental and simplest search method. It is an exhaustive searching technique where every element of a given list is compared one by one with the key until a match is found or the entire list has been traversed.
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"
def linearSearch(list, key):
# Function to perform linear search
for index in range(0, len(list)):
if list[index] == key:
return index + 1 # Position of key in list
return None # Key is not in list
The computational work done by linear search depends on the position of the key in the list:
Technical Profile: Linear Search
Binary Search is an efficient search technique that makes use of the ordering of elements in a sorted list. It works on the principle of divide-and-conquer, repeatedly halving the search space to locate the key.
BinarySearch(numList, key)
Step 1: SET first = 0, last = n-1
Step 2: Calculate mid = (first + last) // 2
Step 3: WHILE first <= last REPEAT Step 4
Step 4: IF numList[mid] == key
PRINT "Element found at position", mid+1
STOP
ELSE
IF numList[mid] > key, THEN last = mid - 1
ELSE first = mid + 1
Step 5: PRINT "Search unsuccessful"
def binarySearch(list, key):
first = 0
last = len(list) - 1
while first <= last:
mid = (first + last) // 2
if list[mid] == key:
return mid
elif key > list[mid]:
first = mid + 1
else:
last = mid - 1
return -1
Technical Profile: Binary Search
Hashing is a technique that allows searching in a single step ($O(1)$ average time complexity) by mapping keys directly to indices in a hash table using a mathematical formula called a hash function .
A simple hash function for numeric values is the remainder method, which divides the element by the size of the hash table and uses the remainder as the index:
$$h(\text{element}) = \text{element} \% \text{size}(\text{hash table})$$
A collision occurs when two or more keys map to the same hash value (e.g., 16 and 26 both map to index 6 when using modulo 10). Resolving this is called collision resolution .
A perfect hash function maps every key to a unique index, completely avoiding collisions.
Technical Profile: Hashing
| Core Computer Science Concept | Technical Definition / Operational State | Structural Parameters & Specifications | Computational Function & System Purpose |
|---|---|---|---|
| Linear Search | Sequential, element-by-element comparison across a collection. | Works on unordered lists; time complexity is $O(n)$. | Locates elements in small or unsorted datasets without sorting overhead. |
| Binary Search | Logarithmic search by repeatedly halving a sorted search space. | Requires sorted lists; time complexity is $O(\log n)$. | Enables rapid retrieval in large, static, ordered datasets. |
| Hashing | Direct mapping of keys to table indices using a mathematical function. | Requires a hash table and hash function; average time complexity is $O(1)$. | Provides constant-time search and retrieval for high-performance databases. |
Consider a sorted database containing $2^{30}$ ($1,073,741,824$) records. If the target record lies exactly at the middle position, compare the efficiency of linear search and binary search.
Socio-Technical Analysis & Core Systemic Impact: Since the target record lies at the middle position, linear search would require $2^{29}$ ($536,870,912$) comparisons to reach the middle. In contrast, binary search calculates the middle index in its very first iteration, finding the record in exactly $1$ comparison. This highlights the massive computational savings of binary search for middle-element queries, reducing execution time from hours to microseconds.