BINARY SEARCHING & BINARY INSERTION

1. BINARY SEARCH
Binary searching is a technique for locating items in a sorted list.

Binary searching gets its name from the fact that you continually divide the data in half,
progressively narrowing down the search space until you find a match or there are no more
items to process.

Real life Examples

1. Searching for a verse in the Bible or Koran

2. Searching for a word in the dictionary
3. Searching for a Key expression/word in the Encyclopedia
4. Looking for a chapter in a book

A binary search involves continually dividing the data in half —hence, binary—and
searching the lower or upper half as appropriate.

The Steps
The steps involved in performing a binary search can be summarized as follows:
1. Start in the middle of the list.
2. Compare the search key with the item at the current location.
3. If the search key is at the current location, then you are done.
4. If the search key is less than the item at the current location, then it must be in the lower
half of the data (if it exists at all) so divide the list in two and go to step 1, using the lower
half.
5. Otherwise, it must be in the upper half of the list (again, if it exists at all), so go to step 1,
using the upper half.

Example:
Given the sorted 13-element list:
15, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 85, 88
(i). Use Binary Search to find the location of 40
(ii). Use Binary Search to find the location of 80

SOLUTION:
Given the sorted 13-element list:
15, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 85, 88
 (i). Using Binary Search to find the location of 40:
1 2 3 4 5 6 7 8 9 10 11 12 13 Positions of the given data
15, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 85, 88
Mid-position = (1+13)/2 = 7
Step 1: 15, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 85, 88
Mid-position = (1+6)/2 = 3
Step 2: 15, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 85, 88
Mid-position = (4+6)/2 = 5
Step 3: 15, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 85, 88

Given the sorted 13-element list:

15, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 85, 88

(ii). Using Binary Search to find the location of 80:

1 2 3 4 5 6 7 8 9 10 11 12 13 Positions of the given data
15, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 85, 88
Mid-position = (1+13)/2 = 7
Step 1: 15, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 85, 88
Mid-position = (8+13)/2 = 10
Step 2: 15, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 85, 88
Mid-position = (11+13)/2 = 12
Step 3: 15, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 85, 88
Mid-position = (11+11)/2 = 11
Step 4: 15, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 85, 88

Another Example:

Given the following sorted list of nine letters in Figure 1, use Binary Search to search for the
letter K.

Figure 1: List containing nine letters in ascending sorted order.

You start the search in the middle of the list by comparing the search key with the letter I, as
shown in Figure 2.
 Figure 2: A search always begins with the middle item.

Because you haven’t yet found a match, you divide the list in half. Then, because the search
key, K, sorts higher than the current item, you concentrate your efforts on the upper half (see
Figure 3).

Figure 3: The search key must exist somewhere in the upper half of the list.

The new list consists of four letters: K, L, M, and P—an even number. Finding the middle
item in a list containing an even number of items is clearly nonsensical. Luckily, though, it
doesn’t really matter whether the two halves are strictly equal, so you can arbitrarily choose
one of the two middle items: Lor M. This example uses L(see Figure 4).

Figure 4: The search continues with the “middle” item.

Now you compare the search key with the chosen middle item—L. Once again, it’s not the
item you are looking for, so you divide the list in two and try again. This time, however, the
search key sorts lower than the current item—K sorts before L—so you can assume that it
will be found in the lower half, if indeed it exists at all.

Figure 5 shows that the search finally narrows to only one item, K, which in this case is the
one you were looking for.

Figure 5: The search finally narrows to only one item.

 The search is complete and you managed to locate the key in only three comparisons: the
two intermediary comparisons with I and L, and the final comparison that resulted in the
match.

2. Binary Insertion
Binary insertion is a technique based on binary searching that enables you to maintain your
data in sorted order. Clearly, you could use some of the sorting algorithms already covered
in this book to keep your data in order, but as we will show, performing a sort after every
insertion into a list can be very expensive. Indeed, performing a sort even after all of the data
has been added to a list still turns out to be relatively more expensive than inserting the data
in sorted order right from the start.

Binary insertion works pretty much like binary searching. In fact, the only difference
between the two is that a binary search returns the position of the search key within the data,
and a binary insert, as the name suggests, inserts the new key into the list at the appropriate
position.

Imagine you wanted to insert the letter G into the sorted list of letters defined below:

As with a binary search, you start at the middle item, I. Comparing the I with the new value,
G, you determine that the insertion point must lie in the lower half of the list (I sorts lower
than G).

Figure (i) shows that the next letter you compare against is the D. This time, the new value
sorts higher than the current item, so you need to concentrate on the upper half of the
remaining list.

Figure (i): The search moves to the lower half of the list.

You’re now down to only two letters: F and H.

Figure (ii) shows that our new value sorts higher than the current item, F, so look to the H, as
shown in Figure (iii).

Figure (ii): The search moves to the upper half of the remaining list.

The new value, G, sorts lower than the current item, H, but this time you have no more items
to compare against; it’s time to perform the insertion.

Figure (iii): The search narrows to only one item.

The new value belongs before the last item, so you shift all the elements after and including
the H to the right one position to make room for G, as shown in Figure (iv).

Figure (iv): The key is inserted so as to maintain the correct ordering.

You can then insert the G into the correct position that ensures that the ordering of the list is
maintained.

Now that you know how binary insertion works, you can write some code to actually
perform a binary insertion into a list.
Summary

In this lecture, you have learned the following key points:

1. Binary searching uses a divide-and-conquer approach to locating a search key.

2. Binary searching works best when used with a data structure that supports fast, index-
based lookup.
3. Binary insertion builds on binary searching to add items to a list
4. Binary insertion proves to be very efficient, performing as well as (and arguably better
than) some of the sorting algorithms.

Binary Search implementation on Arrays and Linked Lists

Can binary search work effectively on the data structures below:
i. sorted array
ii. sorted linked list ?
Explain your answer for each.

The binary search algorithm (Divide and conquer approach) is dependent on the data it works
on to be sorted, continuously finding the mid-section of data and discarding part of the data
that is not required.

The singly linked list data structure’s access to elements in the structure is sequential, so to
find the middle of the linked list it can only do this by traversing the structure. The binary
search will continuously traverse the linked list to find the middle section before discarding
the data it does not want making its search operation O(n) + O(logn) => effectively O(n)
this makes binary search on linked list inefficient.

With an array access, random finding the mid-section every time of an array is a constant
operation as it discards the section of data it does not need this makes the total operation O(1)
+ O(logn) => O(logn) this makes binary search on linked list efficient.