Searching

In this section we will study searching. Searching is the algorithmic process of finding a particular item in a collection of items. A search typically answers either True or False as to whether the item is present. On occasion it may be modified to return where the item is found. For our purposes here, we will simply concern ourselves with the question of membership.

In Python, there is a very easy way to ask whether an item is in a list of items. We use the in operator.

>>> 15 in [3, 5, 2, 4, 1]
False
>>> 3 in [3, 5, 2, 4, 1]
True

Given the ease of conducting a search in Python, you may wonder what the purpose is of studying search as an algorithms problem. The answer is that the underlying process used to enable a search is important to understand as it arises elsewhere, such as in data structures designed for fast search, and particular in databases.

It turns out that there are many different ways to search for an item in a collection. We focus here on the difference between two such ways—sequential search and binary search.

Next: The Sequential Search

Practical Algorithms and Data Structures

Introduction

Analysis

  1. The Big Picture
  2. Big O Notation
  3. An Anagram Detection Example
  4. Performance of Python Types

Stacks

  1. Introduction to Stacks
  2. A Stack Implementation
  3. Balanced Parentheses
  4. Converting Number Bases
  5. Infix, Prefix and Postfix Expressions

Queues

  1. Introduction to Queues
  2. A Queue Implementation
  3. Simulating Hot Potato

Deques

  1. Introduction to Deques
  2. A Deque Implementation
  3. Palindrome Checker

Lists

  1. Introduction to Lists
  2. Implementing an Unordered List
  3. Implementing an Ordered List

Recursion

  1. Introduction to Recursion
  2. Calculating the Sum of a List of Numbers
  3. The Three Laws of Recursion
  4. Converting an Integer to Any Base
  5. Tower of Hanoi
  6. Dynamic Programming

Searching

  1. Searching
  2. The Sequential Search
  3. The Binary Search
  4. Hashing

Trees

  1. Introduction to Trees
  2. Representing a Tree
  3. Parse Trees
  4. Tree Traversals
  5. Priority Queues with Binary Heaps
  6. Binary Search Trees
  7. AVL Trees

Graphs

  1. Introduction to Graphs
  2. Representing a Graph
  3. Word Ladders
  4. A Knight’s Tour
  5. General Depth First Search
  6. Topological Sorting
  7. Shortest Path with Dijkstra’s Algorithm
  8. Strongly Connected Components
  9. Prim’s Spanning Tree Algorithm