We live in the sea of information. It gets even more serious with the Internet. Think about all the information and data sorted globally waiting to be shared. We often need to find one particular item amongst so many of them. There are too many examples to name a few - trying to find someone's phone number on your phone, the most popular Ethiopian restaurant in Colorado, how to interpret a dream you had last night, 1998 Super bowl Winner, ...
This is why fast searching algorithms are critical. If you linearly (sequentially) traverse each item in an available data set-for example of each phone number in your phone - individually, to see whether it is what you are looking for, in a very large set of data, it will take a few hours or days to finish it. Instead, the binary searching algorithm can be used to help find the item in a much shorter time.
However, with un-preprocessed data (completely random data), there is no way you can do better than linear search (a. k.a. sequential search, Textbook page 211). But, if the data is pre-processed (sorted), then you can use the Binary Search (wiki) algorithm to mprove the search time dramatically. In this 3/6/2021 Program Assignment 4 - Searching, Sorting, and Drawing shapes (Mar 14) you are asked to implement the basic binary search algorithm and the insertion sorting algorithms. You will learn more about these two topics (Sorting and Searching) when you take Data Structure and Algorithms classes.
Binary search: the most fundamental searching algorithm within a sorted array. It finds the position of a target value by comparing the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array. This algorithm takes logarithmic time (log n) (big-oh of log ncomparisons where n is the number of elements in an array. (Don't worry too much about Big-O notation if you don't understand it now)
Based on this binary search algorithm, we want to play a well-known guessing game that guarantees to find the target value in log n times. (1 Billion vs 30, 1Trillion vs 40 searches) Please read the following article for more information about the binary search: Following is what you are asked to do in C++: The function and file names are just examples. You may pick up your own name.