13.6. Example 2: Searching Algorithms

Searching algorithms help in finding an element in a list. Let’s look at Linear Search and Binary Search.

Searching algorithms are fundamental in computer science and programming because they provide methods for locating elements in data structures like arrays or lists. They can be broadly categorized, and in this section, we focus on two specific types: linear search and binary search. Understanding these algorithms is essential for optimizing data retrieval, which is a common task in software development.

Imagine you are looking for a specific book in a library. If the books are scattered randomly on the shelves, you would likely check each one until you find the one you want—this represents a linear search. However, if the books were sorted alphabetically, you could quickly narrow down your search to specific sections—this is similar to how a binary search operates.

Linear Search checks each element of the list sequentially to find the target value.

Steps:

1. Start from the first element of the list.
2. Compare each element with the target value.
3. Return the index if a match is found; otherwise, return -1.

Example:

public class LinearSearch {
public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i; // Target found
}
}
return -1; // Target not found
}
public static void main(String[] args) {
int[] arr = {10, 20, 30, 40, 50};
int target = 30;
int index = linearSearch(arr, target);
System.out.println("Element found at index: " + index); // Output: Element found at index: 2
}
}

Time Complexity: O(n)

The linear search algorithm performs a straightforward task of checking each element in a list one by one until it finds the target value. The algorithm begins from the first element and iterates through the entire list, comparing each element to the target. If it finds a match, it returns the index of that element; if it finishes checking all elements and does not find a match, it returns -1 to indicate that the target was not found. The time complexity of linear search is O(n), reflecting that in the worst case, it may need to check every element.

Think about looking for a specific name in a phonebook. You would start at the first name and go down the list, one by one, until you find the name you're looking for or reach the end of the book. This is what linear search does; it’s a very manual approach, but it guarantees that you will find the target if it's present.

Binary Search is a more efficient searching algorithm that works on sorted arrays. It repeatedly divides the search interval in half.

Steps:

1. Find the middle element of the list.
2. If the middle element is equal to the target value, return its index.
3. If the target value is smaller, repeat the search in the left half; otherwise, search in the right half.

Example:

public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid; // Target found
}
if (arr[mid] < target) {
left = mid + 1; // Search in right half
} else {
right = mid - 1; // Search in left half
}
}
return -1; // Target not found
}
public static void main(String[] args) {
int[] arr = {10, 20, 30, 40, 50};
int target = 30;
int index = binarySearch(arr, target);
System.out.println("Element found at index: " + index); // Output: Element found at index: 2
}
}

Time Complexity: O(log n)

Binary search is an efficient searching algorithm that operates on sorted arrays. The process begins by identifying the middle element of the array. If this middle element is equal to the target value, the search is complete. If the target value is smaller than the middle element, the search continues in the left half of the array; if it's larger, the search shifts to the right half. This method effectively reduces the search space by half each time, leading to a time complexity of O(log n), which is much faster than linear search for large datasets.

Consider using a dictionary to find the definition of a word. Instead of flipping through the pages from the very start to find the word, you first open to the center of the dictionary and check if the word comes before or after that point. You then discard half of the pages and repeat the process until you find the word or determine it’s not there. This method of narrowing down is analogous to how binary search functions.

--