19.1 Algorithms: Linear and Binary Searching

This section explores two fundamental searching algorithms: linear search and binary search. Understanding these algorithms is crucial for analyzing the efficiency of data retrieval.

Linear Search

Linear search is the simplest searching algorithm. It involves sequentially examining each element in a list until the target value is found or the entire list has been searched.

How it works:

1. Start at the beginning of the list.
2. Compare the current element with the target value.
3. If the current element matches the target value, the search is successful.
4. If the current element does not match the target value, move to the next element in the list.
5. Repeat step 3 and 4 until the target value is found or the end of the list is reached. If the end of the list is reached without finding the target value, the search is unsuccessful.

Pseudocode:

function linearSearch(list, target)  for each element in list do    if element == target then      return index of element    end if  end for  return -1  // Target not foundend function

Efficiency:

• Best Case: The target value is the first element in the list. Time complexity is O(1).
• Average Case: The target value is in the middle of the list. Time complexity is O(n).
• Worst Case: The target value is the last element in the list or not present. Time complexity is O(n).

Table summarizing Linear Search:

Binary Search

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

How it works:

1. Start with the entire sorted list as the search interval.
2. Find the middle element of the search interval.
3. If the middle element matches the target value, the search is successful.
4. If the target value is less than the middle element, the search continues in the left half of the interval.
5. If the target value is greater than the middle element, the search continues in the right half of the interval.
6. Repeat steps 2-4 until the target value is found or the search interval is empty.

Pseudocode:

function binarySearch(list, target)  low = 0  high = length of list - 1  while low <= high do    mid = (low + high) / 2  // Integer division    if list[mid] == target then      return mid    else if list[mid] < target then      low = mid + 1    else      high = mid - 1    end if  end while  return -1  // Target not foundend function

Efficiency:

• Best Case: The target value is the middle element in the list. Time complexity is O(1).
• Average Case: The target value is found after a logarithmic number of comparisons. Time complexity is O(log n).
• Worst Case: The target value is not in the list or is at the extreme ends. Time complexity is O(log n).

Table summarizing Binary Search:

Important Note: Binary search requires the input list to be sorted. If the list is not sorted, the algorithm will not produce correct results.