SEARCHING:  you have some data, you want to find one specific record from a possibly very large collection of data.

Binary Search:  Binary search ONLY works on a sorted array.  (For example, if you have your information in a linked list, Binary Search won't work.)

0 APPLE
1 BANANA
2 CANTALOUPE
3 DRAGONFRUIT
4 ELDERBERRY
5 FIG
6 GRAPEFRUIT
7 HONEYDEW

F   L   T
0   7   (0+7)/2 = 3  DRAGONFRUIT  I WIN.

0   7   (0+7)/2 = 3  DRAGONFRUIT:  TOO HIGH

0   2   (0+2)/2 = 1  BANANA  I WIN

0   7   (0+7)/2 =3   DRAGONFRUIT:  TOO LOW

4   7   (4+7)/2 = 5  FIG:  TOO HIGH

4   4   (4+4)/2 = 4  ELDERBERRY  I WIN.

Let's look for GRAPE

0   7   (0+7)/2 = 3  DRAGONFRUIT:  TOO LOW

4   7   (4+7)/2 = 5  FIG:  TOO LOW

6   7   (6+7)/2 = 6  GRAPEFRUIT:  TOO HIGH

6   5   OUT OF ORDER:  NOT THERE but would fall between positions 5 and 6:  FIG and GRAPEFRUIT

So, binary search if it's there, finds it.  If it's not there, it lets you know where it would be if it were there.

If the information is in a sorted array, binary search is the absolute fastest search algorithm there is.  It beats and AVL tree.  It beats everything.

The downside is that it only works on sorted arrays.  Why is this a problem?

Has to be sorted.
Has to be an array.

They are pretty much static.  If you want to add or delete anything, you've got to remake the array.  Adding something or deleting something while keeping the array sorted is going to O(n) time.  The actual binary search takes O (lg n) time.  So adding and deleting, while possible, takes a long time.  BUT binary search is perfectly appropriate for static lists (lists that don't change) or that change infrequently.  But this is why things like AVL or Red-Black Trees or B-Trees were developed.  You can add, delete, or search in O(lg n) time.  These structures are designed for data that is more dynamic.  However, although you can search an AVL tree in O(lg n) time, the binary search is still a shade faster.