PDE - Binary Search (Lesson)

Binary Search

It Has to Do With 2

Binary, as we learned earlier in the year has the bi at the front of the word which means twice or 2 in Latin.  All words starting with bi have a 2 meaning, i.e. bicycle means 2 wheels.

Thus the binary search, a search that divides data in half to decrease the amount of processing time needed. 

Example:  Suppose you have 10 numbers 1 - 15 located in an array at indices 0 - 14. How can we find the number 10 with the least amount of checking.  Use the chart below for analysis assistance.

1.  Using a linear search, each data value is checked starting with index 0, the data items would be checked 10 times to get to the number 10,  Each of the numbers 1 through 9, data,  would be compared to 10 prior to finding 10 in the set on the 10th comparison.

2.  Using a binary search (find the division by 2):

• Low index is 0 and high is 15, so 15 + 0 = 15
• Divide 15 in half and you will get the integer 7 (index is a whole number, so leave off the remainder).
• Check is the value at index 7 which would be 8 <, =, or >  then 10.  It is <.
• Add 1 to a 7 and begin to repeat steps (no extra code, but the steps will continue below)
• Low index is 8 and high is 15, so 15 + 8 = 23
• Divide 23 in half and you will get the integer 11 (index is a whole number, so leave off the remainder).
• Check is the value at index 11 which would be 12 <, =, or >  then 10.  It is >.
• Set high index to 11 - 1 and and repeat process.
• Low index is 8 and high is 10, so 10 + 8 = 18
• Divide  18 in half and you will get the integer 9 (index is a whole number, so leave off the remainder).
• Check is the value at index 9 which would be 10 <, =, or >  then 10.  It is =.  
• Found the number in 3 checks to the data set versus 10 in a linear search.

Notes concerning the above binary search

1. With the first division by 2 to get the index 7 and the comparison check for <. =. > note that all of the indices < 7 were eliminated from consideration.  Note 7 was just compared.
2. With the second division by 2 to get the index 11 and the comparison check for <. =. > note that all of the indices > 12 were eliminated from consideration.  Note 11 was just compared.
3. With the third division by 2 to get the index 9 and the comparison check  for <, =, > note that all of the = causes no more need to check.
4. In a large data set this is a search that allows for quickness due to eliminating halfs of the data set with each look, but the set must be ordered.  If the set is not ordered, the overhead of getting the set ordered must be accounted for.

Two Sets of Binary Code

The code below provides the initial setup of information and call to the getBinarySearch function (method).

Setup with a solid ordered array

This array is written with all numbers inclusive between 10 and 25.  Thus there are not any gaps.   A random number is pulled between 10 and 25 to search for.

Note:  

• The call to the getBinarySearch procedure and the passing of the array and the number to find in the array. 
• The whole number (integer) is required to be returned so the calling statement has a variable to catch the returning value.
• Initial check upon a value being returned to notFoundBinary to handle the -1, a standard use of the number to mean not found in code.

Setup with a ordered array with scattered numbers

Note:

• The while loop used to set up an output message of the entire array being processed. 
• The concatenation of string text (textString) is important to understand for its versatility in building output information.  A manual setup process of the concatenation with math items was used earlier in the course.  With loops and arrays there are added possibilities to create a text from data.
• The call to the getBinarySearch procedure and the passing of the array and the number to find in the array. 
• The whole number (integer) is required to be returned so the calling statement has a variable to catch the returning value.
• Initial check upon a value being returned to notFoundBinary to handle the -1, a standard use of the number to mean not found in code.

Notice the similarities in the two code files above.  Were two really needed?   There is little difference except displaying the array.  Maybe that could be an option for a specific request or size.  Both of these structures could process either array.  The creation of more items that are standard, reducing complexity by not being redundant greatly helps programming efficiency (design consistency) as well as code efficiency.  The consolidation to one set of initial setup of the call to search the binary array would decrease debug time as only one set of code would need to be considered and definitely not two programs to keep up with. 

getBinarySearch Method

The purpose of the binary search is to save processing time when searching large data sets by eliminating half of the set from consideration each time an data item is checked.  Funtionally, the getBinarySearch method accepts a whole number (integer) array and the number to be found, nbrToFind.  Control is based on the while loop with the highIndex >= lowIndex for the loop to run, effectively stopping the loop if these items reverse.  the lowIndex is initially set to zero and highIndex to the last element in the array, binarySearchAarray.length - 1.  These numbers are adjusted as the nbrToFind is evaluated as being below, equal, or above the half data value of the array to eliminate the half of the array that the number will not be found in within the ordered array. Division by 2 continues with the data set until the nbrToFind is found or not Found (-1). Once found the index of the nbrToFind is returned, eliminating the need to progress through the complete set to save computer processing time. The getBinarySearch method reduces complexity by having code to debug or add to in one place for this search process.

Note:

• Various debug and walkthru displays have been left in the code for you to be able to do a trace with the video.
• The default return of -1 if the nbrToFind is not found.

Both of the videos below contain the output statements for you to follow with the code for tracing.  Tracing is the process of reading code to decide what the out put should be or finding out how the code does or does not work.

getBinarySearch video for ordered solid numbers                                                getBinarySearch video for ordered missing numbers

 

IMAGES AND VIDEOS CREATED BY GAVS.