Comment
Earl Joel
binary sort,
November 27, 2008 at 2:11 AM
November 27, 2008 at 2:11 AM
Performance
The advantage of a binary search over a linear search is astounding for large numbers. For an array of a million elements, binary search, O(log N), will find the target element with a worst case of only 20 comparisons. Linear search, O(N), on average will take 500,000 comparisons to find the element. Probably the only faster kind of search uses hashing, a topic that isn't covered in these notes.
This performance comes at a price - the array must be sorted first. Because sorting isn't a fast operation, it may not be worth the effort to sort when there are only a few searches.
Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/** Binary search of sorted array. Negative value on search failure.
* The upperbound index is not included in the search.
* This is to be consistent with the way Java in general expresses ranges.
* The performance is O(log N).
* @param sorted Array of sorted values to be searched.
* @param first Index of beginning of range. First element is a[first].
* @param upto Last element that is searched is sorted[upto-1].
* @param key Value that is being looked for.
* @return Returns index of the first match, or or -insertion_position
* -1 if key is not in the array. This value can easily be
* transformed into the position to insert it.
*/
public static int binarySearch(int[] sorted, int first, int upto, int key) {
while (first < upto) {
int mid = (first + upto) / 2; // Compute mid point.
if (key < sorted[mid]) {
upto = mid; // repeat search in bottom half.
} else if (key > sorted[mid]) {
first = mid + 1; // Repeat search in top half.
} else {
return mid; // Found it. return position
}
}
return -(first + 1); // Failed to find key
}
View All Comments | View Tutorial
The advantage of a binary search over a linear search is astounding for large numbers. For an array of a million elements, binary search, O(log N), will find the target element with a worst case of only 20 comparisons. Linear search, O(N), on average will take 500,000 comparisons to find the element. Probably the only faster kind of search uses hashing, a topic that isn't covered in these notes.
This performance comes at a price - the array must be sorted first. Because sorting isn't a fast operation, it may not be worth the effort to sort when there are only a few searches.
Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/** Binary search of sorted array. Negative value on search failure.
* The upperbound index is not included in the search.
* This is to be consistent with the way Java in general expresses ranges.
* The performance is O(log N).
* @param sorted Array of sorted values to be searched.
* @param first Index of beginning of range. First element is a[first].
* @param upto Last element that is searched is sorted[upto-1].
* @param key Value that is being looked for.
* @return Returns index of the first match, or or -insertion_position
* -1 if key is not in the array. This value can easily be
* transformed into the position to insert it.
*/
public static int binarySearch(int[] sorted, int first, int upto, int key) {
while (first < upto) {
int mid = (first + upto) / 2; // Compute mid point.
if (key < sorted[mid]) {
upto = mid; // repeat search in bottom half.
} else if (key > sorted[mid]) {
first = mid + 1; // Repeat search in top half.
} else {
return mid; // Found it. return position
}
}
return -(first + 1); // Failed to find key
}
View All Comments | View Tutorial
Related Tutorial and Articles
If you are facing any programming issue, such as compilation errors or not able to find the code you are looking for.
Ask your questions, our development team will try to give answers to your questions.
Tutorial Topics
