Searching and hashing are fundamental concepts in computer science and data structures. They are used to efficiently retrieve information from large datasets.
Searching:
The process of finding the desired information from the set of items stored in the form of elements in the computer memory is referred to as ‘searching in data structure’.
- These sets of items are in various forms, such as an array, tree, graph, or linked list.
- Another way of defining searching in the data structure is by locating the desired element of specific characteristics in a collection of items.
Importance of Searching:
- Efficient Search Operations: Four-point searching enables efficient exploration of neighboring elements in a 2D grid or array, allowing for quick identification of the desired element.
- Application in Pathfinding Algorithms: Techniques like Depth-First Search (DFS) and Breadth-First Search (BFS) often utilize four-point searching to traverse grids or graphs efficiently.
- Problem-Solving Approach: Many algorithmic problems involve searching for solutions or specific elements in a structured grid, making four-point searching a valuable problem-solving tool.
- Optimized Exploration: By considering four directions while searching, algorithms can efficiently navigate through data structures and optimize the search process.
Types of Searching
Linear Search:
Linear search, also known as sequential search, is a straightforward searching algorithm that traverses the entire list or array until it finds the desired element.
In other words, Linear search is the simplest searching algorithm that checks every element in the list or array until the desired element is found.
• It has a time complexity of O(n), where n is the number of elements in the list.
• It works well for both sorted and unsorted lists.
Here’s how it works:
- Start from the beginning of the list.
- Compare each element in the list with the target element.
- If the element matches the target, return its index.
- If the end of the list is reached without finding the target, return -1 (indicating the element is not present).
Lets clear the concept of linear search through an example:
public class LinearSearch {
// Method to perform linear search
public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i; // Return the index where target is found
}
}
return -1; // Return -1 if target is not found
}
public static void main(String[] args) {
int[] array = {12, 45, 67, 23, 9, 10, 99};
int target = 23;
int resultIndex = linearSearch(array, target);
if (resultIndex != -1) {
System.out.println("Element " + target + " found at index: " + resultIndex);
} else {
System.out.println("Element " + target + " not found in the array.");
}
}
}
Output:
Element 23 found at index: 3
Complexity Analysis of Linear Search:
- Time Complexity: Linear search has a time complexity of O(n), where ‘n’ is the number of elements in the collection being searched.
- Worst-case Scenario: In the worst-case scenario, linear search may need to iterate through all ‘n’ elements in the collection to find the target element or determine its absence.
- Linear Time Complexity: The time taken by linear search increases linearly with the number of elements in the collection.
Binary Search:
Binary search is a more efficient searching algorithm that requires the list to be sorted that works by repeatedly dividing the search interval in half until the target element is found or the interval is empty.
• This algorithm is significantly faster than linear search, especially in scenarios where the dataset is large, showcasing the importance of efficient searching techniques in DSA.
Here’s how it works:
- Compare the target element with the middle element of the sorted list.
- If the target matches the middle element, return its index.
- If the target is less than the middle element, search the left half of the list.
- If the target is greater than the middle element, search the right half of the list.
- Repeat the process until the target element is found or the interval is empty.
Lets clear the concept of Binary search through an example:
public class BinarySearchExample {
public static int binarySearch(int[] arr, int key) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// Check if key is present at mid
if (arr[mid] == key)
return mid;
// If key is greater, ignore left half
if (arr[mid] < key)
left = mid + 1;
// If key is smaller, ignore right half
else
right = mid - 1;
}
// Key not found
return -1;
}
public static void main(String[] args) {
int[] arr = { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 };
int key = 23;
int result = binarySearch(arr, key);
if (result == -1)
System.out.println("Element not present in the array");
else
System.out.println("Element found at index " + result);
}
}
Output:
Element found at index 5
Complexity Analysis of Binary Search:
- Best Case: O(1) – When the target element is found at the middle position in the first comparison.
- Worst Case: O(log n) – When the target element is not present in the dataset, requiring logarithmic time to traverse the search space.
- Average Case: O(log n) – Binary search operates in logarithmic time on average due to its divide-and-conquer strategy.