#### Overview of this book

C++ is a mature multi-paradigm programming language that enables you to write high-level code with a high degree of control over the hardware. Today, significant parts of software infrastructure, including databases, browsers, multimedia frameworks, and GUI toolkits, are written in C++. This book starts by introducing C++ data structures and how to store data using linked lists, arrays, stacks, and queues. In later chapters, the book explains the basic algorithm design paradigms, such as the greedy approach and the divide-and-conquer approach, which are used to solve a large variety of computational problems. Finally, you will learn the advanced technique of dynamic programming to develop optimized implementations of several algorithms discussed in the book. By the end of this book, you will have learned how to implement standard data structures and algorithms in efficient and scalable C++ 14 code.
Free Chapter
1. Lists, Stacks, and Queues
2. Trees, Heaps, and Graphs
3. Hash Tables and Bloom Filters
4. Divide and Conquer
5. Greedy Algorithms
6. Graph Algorithms I
7. Graph Algorithms II
8. Dynamic Programming I
9. Dynamic Programming II

## Binary Search

Let's start with the standard search problem: say we are given a sorted sequence of positive integers and are required to find out if a number, N, exists in the sequence. There are several places where the search problem shows up naturally; for example, a receptionist looking for a customer's file in a set of files that are kept ordered by customer IDs or a teacher looking for the marks obtained by a student in their register of students. They are both, in effect, solving the search problem.

Now, we can approach the problem in two different ways. In the first approach, we iterate over the entire sequence, checking whether each element is equal to N. This is called a linear search and is shown in the following code:

bool linear_search(int N, std::vector<int>& sequence)

{

for (auto i : sequence)

{

if (i == N)

...