I have been reading an Algorythem book to help me better strategize and have a better plan of attack, rather than just dive in and start coding. I still dive in as it seems to help get the creative juices flowing. In the book, the author explains that when he refers to efficiency; he is speaking about the number of steps and algorithm takes to complete. This will lead me to binary searches, but for now, I want to explain the steps on how the book arrives at binary searches.
Think about reading a value in an array. The computer knows to look at the point in memory where the item is stored. So looking up an index in an array is going to take one step, as the computer can jump to this point in the array. Now, let us take a look at a linear search on an array. The computer needs to look at every element in the array until it finds the specific value we have asked it to search for. Depending on where this value is, or if the value is non-existent in the array, this can take as many steps as the length of the array; in other words, this can potentially take N steps. This might not be a big deal with an array the length of 5, but what about an array with a length of 100, 200, 1,000? This can begin to take more and more steps.
Now in comes binary searches. There are some trade-offs, as this will only work with an array that is already sorted. But understanding how it works and how efficient it can be is the main point I want to get across. For a small array like 5, maybe not the most efficient search. Let us say the array has 100 values, this search is now only 7 steps. Let us double that to 200 values, this search grows to a whopping 8 steps. Every time the array is doubled, the amount of steps needed to search grows by 1.
Let us take a look at how this is searching in the array. A binary search works by jumping to the middle point in the array and comparing that value to the value we are searching for. An example would be to an array from 1 to 100, we ask the binary search to look for the number 16; the search jumps to 50 and sees that 16 is less than 50. At this point, the search chops the array in half. The array to be searched is now 1 to 49 as it gets rid of the top half, and the midpoint to be searched is 24. Again the computer sees that 16 is less than 24; so the array is cut in half again and is now 1 to 23. These steps continue until the search finds the value, or determines the value does not exist in the array. In a nutshell, you are checking the middle point in the array, and shrinking the search window to be left or right of that point based on the value relative to the middle point. See below for the algorithm and explanation.
Now that I have an understanding of how this solution is working while searching through an array, it's time to continue reading in order to have a better understanding of when and why would be an appropriate time to use a binary search.
