Searching Algorithms:
Fundamental in computer science, searching algorithms efficiently identify specific elements within a list.
Importance of Searching Algorithms:
Essential for logical problem-solving in coding interviews, competitive programming, and real-world software development across fields like databases, cryptography, bioinformatics, robotics, search engines, IoT, and AI.
Linear Search:
->A simple algorithm that sequentially checks each list element until the target is found or the end of the list is reached.
->Alternatively, it is called a Sequential search algorithm, and is applicable on both sorted and unsorted lists.
Program:
for (int i = 0; i < n; ++i) {
if (arr[i] == target) {
// Element found
break;
}
}
Explanation :
Search Loop:
Use a for loop to iterate through the array from index 0 to n-1.
Check if the current element at index i is equal to the target value.
If a match is found, return the index [Math Processing Error].
No Match Found:
If the loop completes without finding a match, return -1, indicating that the target element is not present in the array.
Time Complexity:
O(N) – worst case (If the target is located at the end of the array).
Binary Search:
Binary search is a classic algorithm that efficiently locates a target value within a sorted array.
Search space
Search space is the range of elements where the algorithm looks for the target value
Prerequisites
Binary search relies on the sorted nature of the data to efficiently locate a specific element by repeatedly dividing the search space in half.
If the data is not sorted, binary search may not work correctly in some cases.
Example:
Finding a Page Number in a Book
Target Page: 309
First Open: 500, and search space is on the left side of the book as 309 < 500
Next Open: 250, and search space is on the right side of the book as 309 > 250
The process continues, narrowing down the search space until the target page, 309, is found.
Program:
int low = 0, high = n – 1;
while (low <= high) {
int mid = low + (high – low) / 2;
if (arr[mid] == target) {
// Element found
break;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid – 1;
}
}
Hashing:
Explanation: Uses a hash function to map keys to indexes, allowing for direct access to the desired element.
Program:
unordered_map<int, int> hashTable;
// Inserting key-value pairs
hashTable[key] = value;
// Searching for a key
if (hashTable.find(target) != hashTable.end()) {
// Element found
}