Understanding Search Algorithms: Binary vs Sequential

Search Algorithms

An important area of study in computer science that involves finding information efficiently.

Binary Search

An algorithm that finds the position of a target value within a sorted array by repeatedly dividing the search interval in half.

Sequential Search

An algorithm that checks each element in a list sequentially until the desired element is found or the list ends.

Google Search

A process where Google's algorithms search through an index of the web rather than the web itself.

Google's Index

An ordered collection of web pages that Google's spider programs collect and organize.

Efficient Algorithm

An algorithm that takes the fewest number of guesses or steps to achieve a result.

Pseudocode

A high-level description of an algorithm that uses the structural conventions of programming but is intended for human reading rather than machine reading.

Guessing Game

A game where players attempt to guess a secret number based on feedback of 'too high', 'too low', or 'just right'.

Maximum Number of Guesses (1-100)

The maximum number of guesses required to find a number between 1 and 100 using an efficient algorithm is 7.

Maximum Number of Guesses (1-500)

The maximum number of guesses required to find a number between 1 and 500 using an efficient algorithm is 9.

Facilitator Role

Records the team's guesses and results during the guessing game and tracks the number of guesses made.

Spokesperson Role

Reports the team's pseudocode algorithm.

Quality Control Role

Tests the algorithm using the widget or by playing the guessing game manually.

Process Analyst Role

Keeps track of the team's progress and assesses performance.

Ordered Collection

A collection where elements are arranged in a specific order, allowing for efficient searching.

Feedback Mechanism

The system of providing responses such as 'too high' or 'too low' based on guesses in the guessing game.

Concept Definitions

Definitions that support understanding of vocabulary related to algorithms for finding values in data sets.

Learning Objectives

Goals set for understanding the strengths and weaknesses of search algorithms and the steps required to find values in data sets.

Time Estimate

The estimated duration to complete a task, in this case, 45 minutes for learning about search algorithms.

Indexing

The process of organizing data in a way that allows for efficient searching.

Collaborative Guessing

A method where team members work together to guess the secret number in the guessing game.

Widget

An interactive tool used to play the guessing game or simulate the search process.

Data Set

A collection of data points from which values can be searched or retrieved.

Algorithm Testing

The process of verifying the effectiveness of an algorithm through practical application.

Binary Search Algorithm

An efficient algorithm for the guessing game problem that repeatedly divides the search space into two and eliminates one half.

Linear Search

A search algorithm that works with any list in any order, but is slower compared to binary search.

Maximum Value for Guessing Game

The maximum number for the guessing game can be set up to 9999.

Secret Number Range

In the guessing game, the secret number can be between 1 and a specified maximum value.

Comparison of Search Algorithms

Binary search is more complex but faster, while linear search is slower but works with any list.

Binary Search Requirements

The list must be in sorted order for a binary search to work.

Linear Search Pseudocode

FOR EACH item in List { IF (item = target) DISPLAY 'Found target!' }

Binary Search Pseudocode

low ← 0; high ← N; middle ← item (low+high)/2; REPEAT UNTIL (middle = target OR low > high) { IF (target < middle) high ← middle - 1; IF (target > middle) low ← middle + 1; middle ← item (low+high)/2; } IF (middle = target) DISPLAY 'Found target!'; ELSE DISPLAY 'Target not in list';

Learning Objective AAP-2.L

Compare multiple algorithms to determine if they yield the same side effect or result.

Learning Objective AAP-2.O.a

Write iteration statements to traverse a list.

Learning Objective AAP-2.O.b

Determine the result of an algorithm that includes list traversals.

Learning Objective AAP-2.P.a

Determine the number of iterations required to find a value in a data set for binary search algorithms.

Learning Objective AAP-2.P.b

Explain the requirements necessary to complete a binary search.

Q-1: Better Choice for Unordered List

Linear search is the better choice for searching an unordered list.

Q-2: Better Choice for Sorted List

Binary search is the better choice for searching a sorted list.

Secret Number Game

A game where the app tells you if your guess is right or wrong, without indicating if it is too high or too low.

Number of Guesses

The initial number of guesses in the guessing game is 0.

Guessing Game Mechanics

You can guess a secret number, and the app will provide feedback on whether your guess is correct.

Search Space

The range of numbers from which a secret number is chosen in the guessing game.

Target in List

The goal of the search algorithms is to find a specific target within a list of items.

Cutting Off Search Space

In binary search, if the target is less than the middle, the top half of the list is eliminated; if greater, the bottom half is eliminated.

Binary Search

A search algorithm that is much faster than linear search but requires the list to be in sorted order.

Linear Search

A slower search algorithm that works with any list in any order.

Binary Search Pseudocode

A set of instructions that describes how to implement the binary search algorithm.

Linear Search Pseudocode

A set of instructions that describes how to implement the linear search algorithm.

Learning Objective AAP-2.O.a

For algorithms involving elements of a list: a. Write iteration statements to traverse a list.

Learning Objective AAP-2.O.b

For algorithms involving elements of a list: b. Determine the result of an algorithm that includes list traversals.

Learning Objective AAP-2.P.a

For binary search algorithms: a. Determine the number of iterations required to find a value in a data set.

Learning Objective AAP-2.P.b

For binary search algorithms: b. Explain the requirements necessary to complete a binary search.

Searching an unordered list

The linear search algorithm is the better choice.

Searching a sorted list

The binary search algorithm is a much more efficient algorithm.

Use of Binary Search

Useful for looking up a word in a Webster's dictionary and looking up a phone number in the phone book given the person's full name.

Use of Linear Search

Can be used for looking up a phone number in the phone book given the person's full name and guessing a secret number between 1 and 100.

Middle Calculation

In binary search, the middle is computed as item (low + high) / 2.

Cutting Off in Binary Search

If target < middle, high is set to middle - 1; if target > middle, low is set to middle + 1.

Display Messages

In both searches, display messages indicate whether the target was found or not.

Sorted Order Requirement

Binary search requires the list to be in sorted order to function correctly.

Efficiency of Binary Search

Binary search is much faster than linear search when the list is sorted.

Efficiency of Linear Search

Linear search is slower but can be applied to any list regardless of order.

Target Not Found

In binary search, if the target is not found, a message indicating 'Target not in list' is displayed.

Iteration Statements

Statements used to traverse a list in algorithms.

Finding Value in Data Set

Determining the number of iterations required to find a value is part of binary search analysis.

Requirements for Binary Search

The list must be sorted for binary search to be applicable.

Linear Search

A search algorithm that checks each element in a list sequentially until the desired element is found.

Binary Search

A more efficient search algorithm that divides a sorted list into halves to locate a desired value.

Secret Number Guessing Game

A game where a player must guess a number between 1 and 100.

Phone Book Search

A method of finding a phone number by checking each entry in order, as it is sorted by last name.

Dictionary Search

A method of looking up a word by checking each entry in order, as it is sorted alphabetically.

Maximum Number of List Elements in Binary Search

For a sorted list of 500 elements, the maximum number of elements examined during a binary search is closest to 10.

Pseudocode Algorithm

A high-level description of an algorithm that uses the structural conventions of programming but is intended for human reading rather than machine reading.

Maximum Guesses for 1 to 100

The maximum number of guesses required to find a number between 1 and 100 using binary search is 7.

Maximum Guesses for 1 to 500

The maximum number of guesses required to find a number between 1 and 500 using binary search is 9.

Best Search Algorithm for Shuffled Deck

The best search algorithm to find the Ace of Spades in a shuffled deck is a linear search.

Everyday Search Problem Example

An example of a search problem in everyday life could be looking for a specific book in a library, which may use a binary search if the books are sorted.