Comment

Earl Joel

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

Advertisements
Advertisements