Searching Algorithms using Python and C++

Introduction to Searching Algorithms

In this article, I will introduce you to the Searching Algorithms in computer science using Python and C++ programming language.

How do I find a person’s phone number in the phone book? How do you find your keys when you have misplaced them? If a deck of cards contains less than 52 cards, how do you determine which card is missing? In all of these cases, we are searching for missing items, which is also a very common task for computer programs.

Introduction to Searching Algorithms

Search algorithms are algorithms that solve the search problem, namely, to retrieve information stored in a data structure, or computed in the search space of a problem domain, either with discrete or continuous values.

There are two types of search algorithms (Binary Search and Linear Search); algorithms which make no assumptions about the order of the data structure and algorithms which assume that the data structure is already in order.

Linear Search:

The simplest search algorithm is a linear search. In linear search, we go through each element of the data structure, in turn, exiting once we find an element that matches the search term or once we reach the end of the list. Our return value is the index at which the search term was found or an indicator that the search term was not found in the list.

You can learn the implementation of linear search below:

Binary Search:

Linear search works well in many cases, especially if we don’t know if our data structure is in order. The downside to linear search is that it can be slow. What if our data structure is already in order? Consider looking up a name in the phone book. The names in the directory are listed in alphabetical order.

The binary search uses the ranking of a list. The idea behind the binary search is that every time we do a comparison, we remove half of the data structure until we find the search term or determine that the term is not on the data structure.

We do this by looking at the middle item in the data structure and determining whether our search term is greater or less than the middle item. If it’s lower, we eliminate the top half of the data structure and repeat our search, starting at the point halfway between the first item and the middle item.

If it’s higher, we eliminate the lower half of the data structure and repeat our search, starting at the point halfway between the middle element and the last element.

You can learn the implementation of binary search below: