Binary Search Chapter Notes | Information and Communication Technology for Grade 12 PDF Download

Introduction

Binary search is an important concept in AP Computer Science Principles, offering an efficient way to find items in a sorted list. This chapter explains how binary search works by comparing it to the simpler linear search method. It describes the process of binary search, which divides a sorted list in half repeatedly to narrow down the search area. The chapter also highlights the importance of sorted data for binary search and its advantages in modern programming. Understanding binary search helps programmers create faster and more efficient search algorithms.

Traversing a List

• Traversing a list means going through its items to find a specific value.
• Linear search (sequential search) checks each item in order, one by one, until the target is found or the list ends.
• Binary search is another method to search a list, but it requires the list to be sorted.

Binary Search Algorithm

• Binary search starts at the middle of a sorted list and compares the middle value to the target.
• If the target is greater than the middle value, the algorithm ignores the lower half of the list.
• If the target is less than the middle value, the algorithm ignores the upper half of the list.
• The process repeats, dividing the remaining list in half each time, until the target is found or all values are checked.
• Example:
  • List: 1, 1, 2, 3, 3, 4, 5, 7, 9, 11, 12
  • Searching for 12:
    • Step 1: Check middle value (4). Since 12 > 4, ignore 1, 1, 2, 3, 3, 4.
    • Step 2: New list: 5, 7, 9, 11, 12. Check middle value (9). Since 12 > 9, ignore 5, 7, 9.
    • Step 3: Continue until 12 is found.
• Binary search is faster than linear search because it eliminates half the list each step.
• It is commonly used in modern programs due to its efficiency.
• The list must be sorted (ascending or descending) before using binary search.

Key Terms

• Binary Search Algorithm: An efficient method that repeatedly halves a sorted list, discarding half of the remaining elements each time, until the target is found or determined to be absent.
• Linear Search Algorithm: A basic method that checks each element in a list one by one until the target is found or the list is fully traversed.
• Sequential Search: Another term for linear search, where elements are examined in order until the target is located or the end is reached.
• Sorted Data Set: A collection of data organized in a specific order, such as ascending or descending, based on numerical or alphabetical criteria.