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.