Java Reference
In-Depth Information
return
mid;
12
13
else
14 low = mid +
1
;
15
16
17
second half
}
return
-low -
1
;
// Now high < low, key not found
18 }
19 }
The binary search returns the index of the search key if it is contained in the list (line 12). Oth-
erwise, it returns
-low - 1
(line 17).
What would happen if we replaced
(high >= low)
in line 7 with (
high > low
)? The
search would miss a possible matching element. Consider a list with just one element. The search
would miss the element.
Does the method still work if there are duplicate elements in the list? Yes, as long as the
elements are sorted in increasing order. The method returns the index of one of the matching
elements if the element is in the list.
To better understand this method, trace it with the following statements and identify
low
and
high
when the method returns.
int
[] list = {
2
,
4
,
7
,
10
,
11
,
45
,
50
,
59
,
60
,
66
,
69
,
70
,
79
};
int
i = BinarySearch.binarySearch(list,
2
);
// Returns 0
int
j = BinarySearch.binarySearch(list,
11
);
// Returns 4
int
k = BinarySearch.binarySearch(list,
12
);
// Returns -6
int
l = BinarySearch.binarySearch(list,
1
);
// Returns -1
int
m = BinarySearch.binarySearch(list,
3
);
// Returns -2
Here is the table that lists the
low
and
high
values when the method exits and the value
returned from invoking the method.
Method
Low
High
Value Returned
binarySearch(list, 2)
0
1
0
binarySearch(list, 11)
3
5
4
binarySearch(list, 12)
5
4
-6
binarySearch(list, 1)
0
-1
-1
binarySearch(list, 3)
1
0
-2
Note
Linear search is useful for finding an element in a small array or an unsorted array, but it
is inefficient for large arrays. Binary search is more efficient, but it requires that the array
be presorted.
binary search benefits
There are many strategies for sorting elements in an array. Selection sort and insertion
sort are two common approaches.
Key
Point
Sorting, like searching, is a common task in computer programming. Many different algo-
rithms have been developed for sorting. This section introduces two simple, intuitive sorting
algorithms:
selection sort
and
insertion sort
.
selection sort
insertion sort
