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 found
end 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:

Case	Time Complexity
Best Case	O(1)
Average Case	O(n)
Worst Case	O(n)

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 found
end 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:

Case	Time Complexity
Best Case	O(1)
Average Case	O(log n)
Worst Case	O(log n)

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