Data Structures and Algorithms Using Python

In this chapter we will discuss two important operations in programming languages. These are searching and sorting. There are several algorithms for both searching and sorting. Every algorithm has some merits and demerits. In this chapter we will discuss some important searching algorithms as well as sorting algorithms. We will discuss the working principles of these algorithms in detail and how they can be implemented in Python, we will derive their time complexity, and finally we will compare them with each other.

13.1 Introduction to Searching

Searching is a process by which we can check whether an element is present within a set of elements or not. If it is present, we can say that the search operation is ‘Successful’ and this process also find the position of the element in the list. But if the element is not present, the search operation is considered as ‘Failure’ and the process terminates with an appropriate failure message. In traditional programming languages searching operations are generally implemented using arrays. In Python we can implement searching algorithms using arrays as well as in-built list data structures. There are several searching algorithms to search for an element from an array/list. Here we will discuss the three most common searching algorithms.

• • Linear Search

• • Binary Search

• • Interpolation Search

Among the above three searching algorithms, to implement linear search the array/list need not be sorted necessarily. But the initial requirement for the other two algorithms is that the array/list must be sorted.

13.1.1 Linear Search

The algorithm which checks each element of a list starting from the first position is known as Linear Search. As this algorithm checks each element in a list sequentially it is also known as Sequential Search. When the elements in a list are unsorted, i.e. not in proper order, this searching technique is used. Suppose we have the following list of elements:

And the key element is 40, i.e. we want to search whether 40 is present in the list or not and if it is present, then we also need to know its position in the list. In case of linear search, we start checking from the beginning of the list, i.e. from the index position 0.