Chapter 5. Finding out an Element Using Searching Algorithms

In the previous chapter, we discussed various techniques to arrange a list by sorting it. Now, in this chapter, we are going to discuss various techniques to search a specific value on a list and find the index where it's stored. Several searching algorithms we are going to discuss in this chapter need a sorted list, so we can apply one of the sorting algorithms we discussed in the previous chapter. By the end of this chapter, we will be able to understand and apply the following searching algorithms:

• Linear search
• Binary search
• Ternary search
• Interpolation search
• Jump search
• Exponential search
• Sublist search

Technical requirements

To follow along with this chapter, including the source code, we require the following:

• Desktop PC or Notebook with Windows, Linux, or macOS
• GNU GCC v5.4.0 or above
• Code Block IDE v17.12 (for Windows and Linux OS), or Code Block IDE v13.12 (for macOS)
• You will find the code files on GitHub at https://github.com/PacktPublishing/CPP-Data-Structures-and-Algorithms

Linear search

Linear search is a simple searching algorithm to find out an item in a list using a sequential method. It means that we start looking at the first item in the list, then move to the second item, the third item, the fourth item, and so on. In Chapter 2, Storing Data in Lists and Linked Lists and Chapter 3, Constructing Stacks and Queues, when we discussed data structure, we designed a searching algorithm for each data structure we had. Actually, the searching algorithm uses a linear searching algorithm.

Developing a linear search algorithm

To refresh our memory about linear algorithms, let's pick a random array that contains {43, 21, 26, 38, 17, 30, 25, 18}. We then have to find the index where 30 is stored. As we can see in the array, 30 is in index 5 (since the array is zero-based indexing); however, if we find an unexisting item, the algorithm should return -1. The following is the method of linear search named LinearSearch():

int LinearSearch(
    int arr[],
    int startIndex...

Binary search

Binary search is a searching algorithm to find the position of the searched value in a list by dividing the list into left and right sublists. Prior to performing this searching algorithm, we have to sort the list using the sorting algorithms we discussed in the Chapter 4, Arranging Data Elements Using a Sorting Algorithm.

Developing binary search algorithm

Suppose we have a sorted array containing these 15 elements {3, 8, 11, 15, 16, 23, 28, 30, 32, 39, 42, 44, 47, 48, 50} and we need to find the position of 16. The first thing the binary search does is to find the middle element, then compares it with the searched value. Since we've got 15 elements on the list, the middle index is 7 (since the array is a zero-based index), and the value of the index is 30. Then, we compare 30 with our searched value, which is 16. Since the middle value is greater than the value we are looking for, the searched value must be to the left of the middle index. So, we can take the left subarray...

Ternary search

Ternary search is a searching algorithm that divides an input array into three subarrays—an array of the first third, an array of the last third, and an array between these two areas. It needs to pick two indexes, which are called middleLeftIndex and middleRightIndex. These two indexes are calculated based on the first index and the last index of the input array.

Developing ternary search algorithm

Suppose we have an array as we have in a binary search, {3, 8, 11, 15, 16, 23, 28, 30, 32, 39, 42, 44, 47, 48, 50}, and want to search for a value of 16. The array contains 15 elements, so we will have the fifth index as the middle-left index (middleLeftIndex = 4), and ninth index as the middle-right index (middleRightIndex = 8). By using these two indexes, we can find the searched value in each area using the ternary search algorithm itself (recursive invocation). The code of a ternary search algorithm in C++ is as follows:

int TernarySearch(
    int arr[],
    int startIndex,
  ...

Interpolation search

Interpolation search is an improvement of the binary search algorithm in picking the middle index. Instead of always picking the middle element to be checked to a searched value like in a binary search, the middle index is not always at the middle position in an interpolation search. The algorithm will calculate the middle index based on the searched value, and pick the nearest element from the searched value. Similar to the binary search, in the interpolation search we have to pass an array we want to search and define the lowest index and the highest index, then calculate the middle index using the following formula:

Developing interpolation search algorithm

Let's borrow the array we used in the binary search algorithm, which is {3, 8, 11, 15, 16, 23, 28, 30, 32, 39, 42, 44, 47, 48, 50}, and find value 16. As we discussed earlier, in binary search, we've got 30, 15, and 23 as the middle index when it runs recursively, before we find the position of 16 (which means it...

Jump search

Jump search is a searching algorithm to find the position of a searched value in a sorted list by dividing the array into several fixed-size blocks, jumping to the first index of the block, then comparing the value of the block's first index with the searched value. If the value of the block's first index is greater than the searched value, it jumps backward to the previous block, then starts a linear search of the block.

Developing jump search algorithm

Suppose we have an array containing {8, 15, 23, 28, 32, 39, 42, 44, 47, 48} elements, and we want to find the position of value 39. We will set the jump step by the square root elements number. Since the element number of the array is 10, the step will be √10 = 3. We will now compare the value of index 0, 3, 6, and 9. When the algorithm compares array[0] with 39, the value of array[0] is lower than the searched value. It then jumps to array[3] and compares its value with 39. Since the value is lower than the searched value, it...

Exponential search

Exponential search is similar to a jump search, since it also divides the input array into several subarrays; however, in exponential search, the step we jump is increased exponentially (2ⁿ). In exponential search, we initially compare the second index (blockIndex = 1), then compare array[1] with the searched value. If the array[1] is still lower than the searched value, we increase the blockIndex exponentially to become 2, 4, 8, and so on, until the array[blockIndex] is higher than the searched value. Then we can perform the binary search to the subarray defined by the blockIndex.

Developing exponential search algorithm

Let's use the array we used in jump search, {8, 15, 23, 28, 32, 39, 42, 44, 47, 48}, to perform an exponential search, and we will also find value 39. First, we apply setblockIndex = 1, then compare array[1] with the searched value, 39. Since 15 is lower than 39, the algorithm sets blockIndex = 2. array[2] is still lower than 39, then moves to array[4]....

Sublist search

Sublist search is used to detect a presence of one list in another list. Suppose we have a single-node list (let's say the first list), and we want to ensure that the list is present in another list (let's say the second list), then we can perform the sublist search to find it. For instance, the first list contains these elements: 23 -> 30 -> 41, and the second list contains these elements: 10 -> 15 -> 23 -> 30 -> 41 -> 49. At a glance, we see that the first list presents in the second list.

The sublist search algorithm works by comparing the first element of the first list with the first element of the second list. If the two values don't match, it goes to the next element of the second list. It does this until the two values match, then checks the succeeding elements of the first list with the succeeding elements of the second list. If all elements match, then it returns true, otherwise, it returns false.

Designing sublist search algorithm

Let's design...

Summary

In this chapter, we discussed various searching algorithms, from the fastest searching algorithm to the slowest searching algorithm. To get a faster searching algorithm, we can use the interpolation search with O(log (log N)), since it can find the nearest middle index from a searched value. The others are binary search with O(log N) and exponential search with O(log i), where i is the index of searched value. The moderate searching algorithm is a jump search, which has O(√N) and the slowest algorithm is a linear algorithm with O(N) complexity, since it has to check all list elements; however, contrary to other searching algorithms we discussed in this chapter, the linear algorithm can also be applied to an unsorted list.

In the next chapter, we are going to discuss several common algorithms that are frequently used in string data type to gain the best performance.

QA section

• What is the simplest search algorithm?
• How does linear search algorithm work?
• Which is fastest—binary search algorithm or ternary search algorithm?
• Why does interpolation search algorithm become an improvement of binary search algorithm?
• If we have to choose between binary search algorithm and exponential search algorithm, which should we pick to get the fastest execution time possibilities?
• What is a similarity between jump search algorithm and exponential search algorithm?
• If we need to detect a presence of one list in another list, which search algorithm should we use?

Further reading

For further reference, you can refer to the following links: 

• https://www.geeksforgeeks.org/linear-search/
• https://www.geeksforgeeks.org/binary-search/
• https://www.geeksforgeeks.org/jump-search/
• https://www.geeksforgeeks.org/interpolation-search/
• https://www.geeksforgeeks.org/exponential-search/
• https://www.geeksforgeeks.org/binary-search-preferred-ternary-search/