Basic Array Searching in C++ - Binary Search (
Page 3 of 4 )
The binary search is a more efficient way of searching an array of data. As an array starts to get large (greater than 16 elements) the binary search is the suggested method of searching. However, the use of a binary search requires that the array be sorted.
The binary search begins by analyzing the middle term of the array. This determines if the target is in the first half or second half of the array. If the target is in the first half of the array there is no need to check the second half of the array. If the target is in the second half of the array there is no need to check the first half of the array. By knowing in which half the target is located, we eliminate the other half from consideration. This eliminates unnecessary searching, which improves performance. So, if we had a target value of 200,000 in an array of one million elements we could get rid of elements from 500,000 to 1,000,000 without searching! This continues until we find the given target or until it is not found.
In the following example we find a target of 4 in a sorted array. We first find what the first, middle, and last indexes are of the array. The middle index is found by:
middle index = (first index + last index)/2
Here we see that 0 is the first index, 2 is the middle index, and 4 is the last index.
|
a[0] |
a[1] |
a[2] |
a[3] |
a[4] |
|
1 |
2 |
3 |
4 |
5 |
Now, we compare the target to the value of the middle index. The value of the middle index is 3, which is greater than the index of 2, meaning that the second half of the array doesn’t need to be considered. We are left with the first half of the array and now repeat the process to find the first, middle, and last indexes. We see that 0 is the first index and 1 is the last index. The middle index is 0 because even though (0 + 1)/2 = 0.5, the value is of data type integer and C++ truncates this making it 0 and does not round the value.
|
a[0] |
a[1] |
a[2] |
a[3] |
a[4] |
|
1 |
2 |
3 |
4 |
5 |
Lastly, we compare the target value to the value of the middle index. The value of the middle index is less than the target value so we end up having the first index of the array equaling the target value. This terminates the searching process and we become successful in finding the target value.
|
a[0] |
a[1] |
a[2] |
a[3] |
a[4] |
|
1 |
2 |
3 |
4 |
5 |
/ 38 
