Binary Searching - Demonstration continued
(Page 4 of 5 )
Now, the mid element is U. The left element is R and the right element is Y. What we are looking for is T. As you can see from the table, the key is not equal to the mid element but is less than it. So we can ignore the elements (U, W, Y) on the right side of the new sub-list (R to Y).
Since we are no longer interested in the right side of the new sub-list, let us make “right,”
right = mid - 1
So the element for the index, “right” is now T. The following table shows the situation.
E | I | O | P | Q | R | T | U | W | Y |
|
|
|
|
| Left mid | Right (key) |
|
|
|
Again, we look for the new mid which is
mid = (5 + 6)/2
= 5.5
Sending the value 5.5 through the parseInt() function, we have
mid = 5
We continue in the same way: the mid element is now R, the left element is also R, and the right element is T. As you can see from the table, the key is not equal to the mid element but is now greater than it. So we can ignore the element (R) on the left side of the new sub-list (R,T).
Since we are no longer interested in the left side of the new sub-list, let us make “left,”
left = mid + 1
So the element for the index, “left” is now T. The following table shows the situation.
E | I | O | P | Q | R | T | U | W | Y |
|
|
|
|
|
| left right mid (key) |
|
|
|
We still look for the new mid which is
mid = (6 + 6)/2
= 6
We still continue in the same way: the mid element is now T, the left element is T, and the right element is T. All three indices point to the same element. As you can see from the table, the key is now equal to the mid. The process ends here.
At this point, you may wonder how the process will end if the key is a letter and does not exist in the list. You can deduce that the iteration terminates just after the “left” index is equal to the “right” index. So if the letter does not exist in the list, this condition will still be reached; no index within the range will be returned, but the total number of rows will be returned. Recall that this value is one unit greater than the maximum index.
I hope you can see that binary search is faster than ordinary search. However this is due to the fact that the list is already sorted. If the list is not sorted, binary search will not make sense.
Note: With binary search, if two or more elements are the same, any of their indices can be returned. The one that is returned depends on which element the binarySearch arrives at first.
Next: Algorithm for Binary Search >>
More JavaScript Articles
More By Chrysanthus Forcha
