Binary Searching - Demonstration of Binary Search
(Page 3 of 5 )
When the values (elements) of an array are in sorted order, there are better search methods than the ordinary search method. When you look up a name in the phone book, you do not start at the beginning and scan (glance) through until you find the name – you use the fact that the names are listed in alphabetical (sorted) order and use some intelligence to jump quickly to the right page and then start scanning.
Binary search deals with a list that is already sorted. The problem is that natural data is not normally sorted. Well, some data is stored sorted. A lot of data is kept in database. When retrieving the data, you can have it sorted by the database engine. You will then be able to use binary search on the sorted result. So even though natural data is not normally sorted, there are many sources of sorted data on which you can do binary search.
In this article, I show you how to sort an array of elements (letters or strings) that are in ascending order. The same principles apply to elements that are in descending order.
Consider the following list:
E I O P Q R T U W Y
We shall look for the letter T. So the key is T. There are 10 elements in the list.
Let the index for the left most element be called “left” – at the moment this is 0.
Let the index for the right most element be called “right” – at the moment this is 9.
Let the whole number obtained from (left + right)/2 be called “mid.”
Mid as defined above is the approximate mid-point index. The expression can result in a whole number and a fraction. We want the result to be an index. Since there is no fractional index, we have to drop the fractional part of the result from the expression. We shall use the top-level JavaScript function named "parseInt()" to obtain the whole number (integer) from the expression.
At the moment left = 0, and right = 9.
mid = (left + right)/2
= (0 + 9)/2
= 4.5
We use the parseInt() function as follows:
mid = parseInt((left + right)/2)
Therefore,
mid = 4
The following table shows the present situation:
E | I | O | P | Q | R | T | U | W | Y |
left |
|
|
| mid |
| (key) |
|
| right |
The mid element is Q. Now, since the array (list) is sorted, we can see from the array (table) that the key is not equal to the mid element, but is greater than the mid element. So we do not have to bother looking for the key on the left side of the array; that is from Q to E. This looks so obvious, but is not obvious to the computer. The computer does not observe or glance or inspect and appreciate things the way we are doing. The computer sorts using logical steps, which I show you in this demonstration.
Since we are no longer interested in the left side of the array, let us make “left,”
left = mid + 1
So the element for the index, “left” is now R. The following table shows the situation.
E | I | O | P | Q | R | T | U | W | Y |
|
|
|
|
| left | (key) | mid |
| right |
The new value for mid is
mid = (5 + 9)/2
= 7
Next: Demonstration continued >>
More JavaScript Articles
More By Chrysanthus Forcha
