Book Image

C++ Data Structures and Algorithms

By : Wisnu Anggoro
5 (1)
Book Image

C++ Data Structures and Algorithms

5 (1)
By: Wisnu Anggoro

Overview of this book

C++ is a general-purpose programming language which has evolved over the years and is used to develop software for many different sectors. This book will be your companion as it takes you through implementing classic data structures and algorithms to help you get up and running as a confident C++ programmer. We begin with an introduction to C++ data structures and algorithms while also covering essential language constructs. Next, we will see how to store data using linked lists, arrays, stacks, and queues. Then, we will learn how to implement different sorting algorithms, such as quick sort and heap sort. Along with these, we will dive into searching algorithms such as linear search, binary search and more. Our next mission will be to attain high performance by implementing algorithms to string datatypes and implementing hash structures in algorithm design. We'll also analyze Brute Force algorithms, Greedy algorithms, and more. By the end of the book, you'll know how to build components that are easy to understand, debug, and use in different applications.
Table of Contents (16 chapters)
Title Page
Copyright and Credits
Packt Upsell
Contributors
Preface
Index

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 3015, and 23 as the middle index when it runs recursively, before we find the position of 16 (which means it...