Note51

0.0 by Claude

13 min read

Chapter 8a: Algorithms for Searching

Subtopic: Searching (Introduction)

Definition

Searching is the process of locating a record (entry) whose key matches a given target key value.

Causes

Not specified in notes

Goals / Objectives

  • To find a record with a key equal to the target key.
  • To retrieve the desired item efficiently.

Importance

  • Searching is a common and essential task in computing.
  • It affects performance, so choosing the right technique matters.

Procedures

  • Accept a target key k as input.
  • Compare k with keys in the collection.
  • If a match is found, return the record (retrieval).
  • If no match is found, return failure.

Advantages & Disadvantages

Not specified in notes

Impact / Effect

  • Time-consuming if not optimized.
  • Performance depends on data arrangement and search method.

Examples

“Searching is an everyday occurrence.” (Fig. 16-1)

Key Takeaways

  • Searching means finding a record with a matching key.
  • It’s a basic but time-sensitive operation in computing.
  • Efficient searching depends on how data is arranged.

Subtopic: Searching Techniques

Definition

Searching techniques are methods used to locate a target value in a data structure.

Causes

  • Need to find specific data in arrays or linked lists.

Goals / Objectives

  • To improve search efficiency based on data type and arrangement.

Importance

  • Choosing the right technique can save time and resources.

Procedures

  • Sequential (Linear) Search: Used for unsorted/sorted arrays and linked lists.
  • Binary Search: Used only for sorted arrays.

Advantages & Disadvantages

Not specified in notes

Impact / Effect

  • Determines how quickly a target can be found.
  • Affects overall algorithm performance.

Examples

  • Sequential search for unsorted/sorted arrays and linked lists.
  • Binary search for sorted arrays only.

Key Takeaways

  • Two main techniques: sequential and binary search.
  • Binary search is faster but needs sorted data.
  • Sequential search works on both sorted and unsorted data.

Subtopic: Sequential Search (Unsorted Array)

Definition

Sequential search (also called linear or serial search) checks each element one by one from the beginning until the target is found or the list ends.

Causes

  • Used when data is unsorted and must be checked sequentially.

Goals / Objectives

  • To find a target value in an unsorted array.

Importance

  • Simple and works on any unsorted list.
  • Useful when data is not organized.

Procedures

Iterative Version

public boolean contains(T anEntry) {
  boolean found = false;
  for (int index = 0; !found && (index < length); index++) {
    if (anEntry.equals(array[index]))
      found = true;
  }
  return found;
}

Recursive Version

public boolean contains(T anEntry) {
  return search(0, length - 1, anEntry);
}
 
private boolean search(int first, int last, T desiredItem) {
  if (first > last)
    return false;
  else if (desiredItem.equals(array[first]))
    return true;
  else
    return search(first + 1, last, desiredItem);
}

Advantages & Disadvantages

Advantages

  • Simple to implement.
  • Works on any unsorted data.

Disadvantages

  • Slow for large datasets.
  • Time complexity is linear.

Impact / Effect

  • Performance depends on position of target.
  • May require checking every element.

Examples

  • Search for 8: found after checking 3 elements.
  • Search for 6: not found after checking all elements.

Key Takeaways

  • Sequential search checks each item one by one.
  • Works on unsorted arrays.
  • Recursive version uses tail recursion.
  • Time complexity is O(n) in average and worst cases.

Definition

Efficiency refers to how fast the search completes based on input size.

Causes

  • Depends on position of target and size of list.

Goals / Objectives

  • To measure performance in best, average, and worst cases.

Importance

  • Helps decide when to use sequential search.

Procedures

  • Best case: O(1) — target is first item.
  • Average case: O(n) — target is in the middle.
  • Worst case: O(n) — target is last or not found.

Advantages & Disadvantages

Advantages

  • Predictable performance.

Disadvantages

  • Linear time even in average case.

Impact / Effect

  • Performance degrades with larger lists.

Examples

“O(n/2) is still O(n)” — average case.

Key Takeaways

  • Sequential search is linear in time.
  • Best case is fast, but average and worst are slow.
  • Efficiency depends on target’s position.

Subtopic: Searching a Sorted Array

Definition

Searching a sorted array means locating a target value in an array where elements are arranged in order.

Causes

  • Data is already sorted, which allows for optimized searching.

Goals / Objectives

  • To improve search efficiency by leveraging sorted order.

Importance

  • Enables faster search compared to unsorted data.
  • Allows use of binary search.

Procedures

  • Use sequential search with early stopping.
  • Return the location of the target if found.

Advantages & Disadvantages

Advantages

  • Can stop early if current value exceeds target.
  • More efficient than searching unsorted data.

Disadvantages

  • Still linear in worst case.

Impact / Effect

  • Reduces unnecessary comparisons.
  • Improves performance slightly over unsorted search.

Examples

Fig. 16-4: Coins sorted by mint dates (1982–2007)

Key Takeaways

  • Sorted arrays allow faster searching.
  • Sequential search can stop early.
  • Binary search becomes possible.

Definition

Binary search is a method that repeatedly divides a sorted array in half to find a target value.

Causes

  • Data is sorted, enabling divide-and-conquer strategy.

Goals / Objectives

  • To find a target value quickly using fewer comparisons.

Importance

  • Much faster than sequential search for large datasets.

Procedures

General Idea

  • Compare target with middle element.
  • If equal → found.
  • If less → search left half.
  • If greater → search right half.

Recursive Algorithm

Algorithm binarySearch(a, first, last, desiredItem)
  mid = (first + last) / 2
  if (first > last)
    return false
  else if (desiredItem == a[mid])
    return true
  else if (desiredItem < a[mid])
    return binarySearch(a, first, mid - 1, desiredItem)
  else
    return binarySearch(a, mid + 1, last, desiredItem)

Recursive Method

private boolean binarySearch(int first, int last, T desiredItem) {
  int mid = (first + last)/2;
  if (first > last)
    return false;
  else if (desiredItem.equals(array[mid]))
    return true;
  else if (desiredItem.compareTo(array[mid]) < 0)
    return binarySearch(first, mid - 1, desiredItem);
  else
    return binarySearch(mid + 1, last, desiredItem);
}

Advantages & Disadvantages

Advantages

  • Fast: O(log n) time.
  • Efficient for large sorted arrays.

Disadvantages

  • Only works on sorted arrays.
  • Not suitable for linked lists.

Impact / Effect

  • Reduces search time drastically.
  • Each comparison halves the search space.

Examples

  • Search for 8: found after 4 comparisons.
  • Search for 16: not found after narrowing to empty subarray.

Key Takeaways

  • Binary search is fast and efficient.
  • Only works on sorted arrays.
  • Each step halves the search space.
  • Recursive version is easier to code.

Definition

Efficiency of binary search refers to how quickly it finds a target in a sorted array.

Causes

  • Depends on array size and target position.

Goals / Objectives

  • To analyze performance in different cases.

Importance

  • Helps determine when binary search is preferable.

Procedures

  • Best case: O(1) — target is at midpoint.
  • Average case: O(log n)
  • Worst case: O(log n) — target not found.

Advantages & Disadvantages

Advantages

  • Very fast for large arrays.

Disadvantages

  • Requires sorted data.
  • Not usable with linked lists.

Impact / Effect

  • Performance improves with larger arrays.
  • Search time grows slowly with input size.

Examples

“Each comparison halves the size of the list under consideration.”

Key Takeaways

  • Binary search is logarithmic in time.
  • Best case is instant; worst case still efficient.
  • Ideal for large, sorted arrays.

Subtopic: Sequential Search of Linked List (Unsorted Chain)

Definition

Sequential search of an unsorted chain means checking each node in a linked list one by one.

Causes

  • Data is stored in nodes without order.

Goals / Objectives

  • To find a target value in a linked list.

Importance

  • Works even when data is not sorted.

Procedures

Iterative Version

public boolean contains(T anEntry) {
  Node currentNode = firstNode;
  while (!found && (currentNode != null)) {
    if (anEntry.equals(currentNode.data))
      found = true;
    else
      currentNode = currentNode.next;
  }
  return found;
}

Recursive Version

private boolean search(Node currentNode, T desiredItem) {
  if (currentNode == null)
    return false;
  else if (desiredItem.equals(currentNode.data))
    return true;
  else
    return search(currentNode.next, desiredItem);
}
 
public boolean contains(T anEntry) {
  return search(firstNode, anEntry);
}

Advantages & Disadvantages

Advantages

  • Simple and works on any linked list.

Disadvantages

  • Linear time.
  • Cannot skip nodes.

Impact / Effect

  • Performance depends on target’s position.
  • May need to traverse entire list.

Examples

Fig. 16-7: Chain of linked nodes

Key Takeaways

  • Works on unsorted linked lists.
  • Can be coded iteratively or recursively.
  • Time complexity is O(n).

Subtopic: Sequential Search of a Sorted Chain

Definition

Sequential search of a sorted chain means checking each node in a linked list in order, stopping early if the current value exceeds the target.

Causes

  • Data is stored in sorted linked nodes.

Goals / Objectives

  • To find a target value efficiently in a sorted linked list.

Importance

  • Allows early termination of search.
  • Improves performance over unsorted chain search.

Procedures

public boolean contains(T anEntry) {
  Node currentNode = firstNode;
  while ((currentNode != null) && (anEntry.compareTo(currentNode.data) > 0)) {
    currentNode = currentNode.next;
  }
  return (currentNode != null) && anEntry.equals(currentNode.data);
}

Advantages & Disadvantages

Advantages

  • Can stop early if current value exceeds target.
  • More efficient than unsorted chain search.

Disadvantages

  • Still linear in worst case.
  • Requires sorted data.

Impact / Effect

  • Reduces unnecessary comparisons.
  • Improves average performance.

Examples

Not specified in notes

Key Takeaways

  • Works on sorted linked lists.
  • Stops early if current value > target.
  • Still O(n) in worst case.

Subtopic: Binary Search on Linked List

Definition

Binary search on a linked list is an attempt to apply binary search logic to a chain of nodes.

Causes

  • Trying to use binary search on non-array data.

Goals / Objectives

  • To improve search speed in linked lists (though impractical).

Importance

  • Highlights limitations of binary search with linked structures.

Procedures

  • Requires finding the middle node.
  • In linked lists, this takes linear time.

Advantages & Disadvantages

Advantages

  • Conceptually fast.

Disadvantages

  • Impractical due to linear-time midpoint access.
  • Loses binary search speed advantage.

Impact / Effect

  • No performance gain.
  • Not recommended for linked lists.

Examples

“Binary search of a chain of linked nodes is impractical.”

Key Takeaways

  • Binary search needs fast access to middle.
  • Linked lists don’t support this.
  • Use sequential search instead.

Subtopic: Choosing a Search Method

Definition

Choosing a search method means selecting the most suitable algorithm based on data type and size.

Causes

  • Different data structures and sizes require different strategies.

Goals / Objectives

  • To optimize search performance.

Importance

  • Right choice saves time and resources.

Procedures

  • Use sequential search for small arrays or unsorted data.
  • Use binary search for large, sorted arrays.
  • Avoid binary search on linked lists.

Advantages & Disadvantages

Advantages

  • Tailors search to context.

Disadvantages

  • Wrong choice can slow down performance.

Impact / Effect

  • Directly affects algorithm efficiency.

Examples

Fig. 16-8: Time efficiency comparison in Big Oh notation

Search TypeBest CaseAverage CaseWorst Case
Sequential (unsorted data)O(1)O(n)O(n)
Sequential (sorted data)O(1)O(n)O(n)
Binary (sorted array)O(1)O(log n)O(log n)

Key Takeaways

  • Use sequential search for small or unsorted data.
  • Use binary search for large, sorted arrays.
  • Binary search is not suitable for linked lists.

Definition

Iterative vs recursive search compares two coding styles for implementing search algorithms.

Causes

  • Different programming approaches to the same logic.

Goals / Objectives

  • To choose the most efficient and readable implementation.

Importance

  • Affects code clarity and performance.

Procedures

  • Recursive sequential search uses tail recursion.
  • Iterative version saves space and time.
  • Binary search is fast, so recursion overhead is minimal.
  • Recursive binary search is easier to code.

Advantages & Disadvantages

Advantages

  • Recursive binary search: easier to implement.
  • Iterative sequential search: more efficient.

Disadvantages

  • Recursion may use more memory.
  • Iterative binary search is harder to code.

Impact / Effect

  • Impacts coding style and resource usage.

Examples

“Recursive sequential search is tail recursion.”

Key Takeaways

  • Recursive binary search is easier to write.
  • Iterative search saves memory.
  • Choose based on context and performance needs.

Subtopic: Exercise 8a.2 – Binary Search Walkthrough

Definition

Exercise 8a.2 demonstrates how binary search works step-by-step on a sorted array.

Causes

  • Target value is 50 in a sorted array.

Goals / Objectives

  • To show how binary search narrows down the search space.

Importance

  • Reinforces understanding of binary search logic.

Procedures

Given array: 5 10 15 20 25 30 35 40 45 50

Steps:

  • mid1 = (0 + 9)/2 = 4 → 25 → 50 > 25 → search [5..9]
  • mid2 = (5 + 9)/2 = 7 → 40 → 50 > 40 → search [8..9]
  • mid3 = (8 + 9)/2 = 8 → 45 → 50 > 45 → search [9..9]
  • mid4 = (9 + 9)/2 = 9 → 50 → found

Advantages & Disadvantages

Not applicable to this topic

Impact / Effect

  • Shows how binary search reduces comparisons.

Examples

Target 50 found at index 9 after 4 comparisons.

Key Takeaways

  • Binary search halves the search space each time.
  • Efficient even for large arrays.
  • Best case: O(1), Worst case: O(log n)

Terminology Clarification

  • Tail recursion (meaning: a recursive call that is the last operation in a function, allowing optimization)
  • Big Oh notation (O) (meaning: a way to describe algorithm efficiency based on input size)

Subtopic: Exercise 8a.1 – Comparing contains(T anEntry) in Linked Lists

Definition

This exercise compares how the contains(T anEntry) method works in unsorted vs sorted linked lists.

Causes

  • Different list arrangements (sorted vs unsorted) affect how the search proceeds.

Goals / Objectives

  • To understand how search logic changes based on list order.
  • To analyze implementation differences.

Importance

  • Helps choose the right search method for different list types.
  • Reveals efficiency trade-offs.

Procedures

Unsorted Linked List

  • Traverse node by node until match is found or list ends.
  • No early stopping.

Sorted Linked List

  • Traverse node by node.
  • Stop early if current value exceeds target.

Advantages & Disadvantages

Unsorted List

  • ✅ Works regardless of order
  • ❌ Must check every node

Sorted List

  • ✅ Can stop early
  • ❌ Requires sorted data

Impact / Effect

  • Sorted list improves performance slightly.
  • Unsorted list may require full traversal.

Examples

Not specified in notes

Key Takeaways

  • Sorted lists allow early termination.
  • Unsorted lists require full traversal.
  • Same method behaves differently based on list order.

Subtopic: Efficiency of Sequential Search on a Chain

Definition

Efficiency measures how fast a sequential search completes in a linked list.

Causes

  • Depends on target position and list length.

Goals / Objectives

  • To evaluate performance in different scenarios.

Importance

  • Helps predict search time and choose optimal method.

Procedures

  • Best case: O(1) — target is first node.
  • Average case: O(n) — target is in the middle.
  • Worst case: O(n) — target is last or not found.

Advantages & Disadvantages

Advantages

  • Simple and predictable.

Disadvantages

  • Linear time even in average case.

Impact / Effect

  • Performance degrades with longer chains.

Examples

Not specified in notes

Key Takeaways

  • Sequential search on a chain is linear.
  • Best case is fast; worst case is slow.
  • Efficiency depends on target’s position.

Subtopic: Review of Learning Outcomes

Definition

A recap of what students should be able to do after completing Chapter 8a.

Causes

Not applicable to this topic

Goals / Objectives

  • Implement sequential and binary search algorithms.
  • Assess their time efficiency.

Importance

  • Confirms mastery of core concepts.

Procedures

  • Apply search algorithms to arrays and linked lists.
  • Analyze performance using Big Oh notation.

Advantages & Disadvantages

Not applicable to this topic

Impact / Effect

  • Prepares students for practical implementation and analysis.

Examples

Not specified in notes

Key Takeaways

  • You should now be able to code and evaluate search algorithms.
  • Understand when to use sequential vs binary search.
  • Know how data structure affects search performance.

Subtopic: To Do

Definition

Recommended follow-up actions for students.

Causes

Not applicable to this topic

Goals / Objectives

  • Reinforce learning through practice and review.

Importance

  • Helps solidify understanding and prepare for assessments.

Procedures

  • Review slides and source code.
  • Read recommended textbook sections.
  • Complete practical questions.

Advantages & Disadvantages

Not applicable to this topic

Impact / Effect

  • Strengthens retention and application skills.

Examples

Not specified in notes

Key Takeaways

  • Review materials and practice exercises are essential.
  • Don’t skip the practical questions.
  • Use source code to understand implementation.

Graph View

Backlinks