Binary Search ONLY works on arrays in alphabetical order (or some sort of order):

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Search for "L"

F=0  L=25   T = 12

Position 12 is M : TOO HIGH

F=0   L=11  T = 5

Position 5 is F:  TOO LOW

F=6  L=11  T = 8

Position 8 is I:  TOO LOW

F=9   L=11  T = 10

Position 10 is K:  TOO LOW

F=11   L=11    T=11

Position 11 is L:  FOUND IT

5 lookups.

If there are n entries in our array.  Using Binary Search, we can find the desired element OR determine that it is not present in

log_2 (n+1) rounded up     lookups are less.

If we have 7 items in our list, we can find it in 3 lookups.

If we have 26 items, we can find it in 5 lookups.

100 items:  7 lookups
1000 items:  10 lookups
1000000 items:  20 lookups
1000000000 items:  31 lookups

Where might this be practical?  (Where might it practical to have information in a sorted array?)

You're searching many times through a database that doesn't change between searches.  (This is called a "static database".)  If the database doesn't change, and you know this, storing it as a flat file and using binary search for your searches is amazing.  However, because it is tedious to make changes to a sorted array.  (If you have to add something or remove something, you have to shift stuff up or down to keep the array sorted, and this is time-consuming), a better data structure should be used to make adding and removing reasonable, while also keeping search reasonable (understanding that it now won't be exactly as fast as binary search).

The binary search also works well with repeated keys.  If you have ties in your array, the binary search will quickly all of them.  You use binary search to find one of the keys.  You use another binary search to find the beginning of the range, and another binary search to find the end of the range.

A B C D D D D D D E
0 1 2 3 4 5 6 7 8 9

F=0  L=9    T = 4   Found a D.

Second binary search for the first D

FF=0  LL=3   TT = 1  B:  So move forward
FF=2  LL=3   TT = 2  C:  So move forward
FF=3  LL=3   TT = 3  D:  So move backward
FF=3  LL=2   OUT OF ORDER  FF=3 is the first D

Third binary search is for the last D

FF=5  LL=9  TT= 7  D:  Move forward
FF=8  LL=9  TT=8   D:  Move forward
FF=9  LL=9  TT=9   E:  Move backward
FF=9  LL=8  OUT OF ORDER  LL=8 is the last D

Practical use for this algorithm:

Imagine a database with fixed-length records; all records are the same length.

Student database:

First four characters:  Academic Year
Next five characters:  Course ID
Next five characters:  Section ID
Next thirty characters:  Last Name
Next twenty characters:  First Name
Next three characters:  Grade

From September 1988 to June 1989:

If I have a flat file (sorted array), I can search on Academic Year and get ALL classes from that year.  I can search on Year+Course  and get all sections from that course.  I can search on Year+Course+Section  and get all students in that section, etc.

Random Access Files:

Sequential Access File:  start from the beginning, read forward through the file until you hit the EOF, then stop.
You can put them on tape.

Random Access File:  jump to the position you want to read (or write) and then read or write there.  (Do not pass Go.  Do not collect $200, just jump to the part of the file you want.)

My binary search isn't searching the WHOLE string, it's only checking the first part of each string to compare it to what is being passed in.