6.5. Returning an Array from a Method
6.7. Searching Arrays
Searching is the process of looking for a specific element in an array; for example, discovering whether a certain score is included in a list of scores. Searching is a common task in computer programming. There are many algorithms and data structures devoted to searching. In this section, two commonly used approaches are discussed, linear search and binary search .
6.7.1. The Linear Search Approach
The linear search approach compares the key element key sequentially with each element in the array. The method continues to do so until the key matches an element in the array or the array is exhausted without a match being found. If a match is made, the linear search returns the index of the element in the array that matches the key. If no match is found, the search returns -1 . The linearSearch method in Listing 6.6 gives the solution.
Listing 6.6. LinearSearch.java
Please trace the method using the following statements:
int [] list = { 1 , 4 , 4 , 2 , 5 , -3 , 6 , 2 }; int i = linearSearch(list, 4 ); // returns 1 int j = linearSearch(list, -4 ); // returns -1 int k = linearSearch(list, -3 ); // returns 5
The linear search method compares the key with each element in the array. The elements in the array can be in any order. On average, the algorithm will have to compare half of the elements in an array before finding the key if it exists. Since the execution time of a linear search increases linearly as the number of array elements increases , linear search is inefficient for a large array.
6.7.2. The Binary Search Approach
Binary search is the other common search approach for a list of values. For binary search to work, the elements in the array must already be ordered. Without loss of generality, assume that the array is in ascending order. The binary search first compares the key with the element in the middle of the array. Consider the following three cases:
-
If the key is less than the middle element, you only need to continue to search for the key in the first half of the array.
-
If the key is equal to the middle element, the search ends with a match.
-
If the key is greater than the middle element, you only need to continue to search for the key in the second half of the array.
Clearly, the binary search method eliminates half of the array after each comparison. Suppose that the array has n elements. For convenience, let n be a power of 2 . After the first comparison, there are n/2 elements left for further search; after the second comparison, there are (n/2)/2 elements left for further search. After the k th comparison, there are n/2 k elements left for further search. When k = log 2 n , only one element is left in the array, and you only need one more comparison. Therefore, in the worst case, you need log 2 n+1 comparisons to find an element in the sorted array when using the binary search approach. For a list of 1024 ( 2 10 ) elements, binary search requires only eleven comparisons in the worst case, whereas a linear search would take 1024 comparisons in the worst case.
The portion of the array being searched shrinks by half after each comparison. Let low and high denote, respectively, the first index and last index of the array that is currently being searched. Initially, low is and high is list.length “1 . Let mid denote the index of the middle element. So mid is (low + high)/2 . Figure 6.11 shows how to find key 11 in the list { 2 , 4 , 7 , 10 , 11 , 45 , 50 , 59 , 60 , 66 , 69 , 70 , 79 } using binary search.
Figure 6.11. Binary search eliminates half of the list from further consideration after each comparison.
The binary search returns the index of the search key if it is contained in the list. Otherwise, it returns -(insertion point + 1) . The insertion point is the point at which the key would be inserted into the list. For example, the insertion point for key 5 is 2 , so the binary search returns -3 ; the insertion point for key 51 is 7 , so the binary search returns -8 .
You now know how the binary approach works. The next task is to implement it in Java, as shown in Listing 6.7.
Listing 6.7. BinarySearch.java
1 public class BinarySearch { 2 /** Use binary search to find the key in the list */ 3 public static int binarySearch( int [] list, int key) { 4 int low = 0; 5 int high = list.length - 1; 6 7 while (high >= low) { 8 int mid = (low + high) / 2 ; 9 if (key < list[mid]) 10 high = mid - 1; 11 else if (key == list[mid]) 12 return mid; 13 else 14 low = mid + 1 ; 15 } 16 17 return -low - 1 ; 18 } 19 } |
You start by comparing the key with the middle element in the list whose low index is and high index is list.length-1 . If key < list[mid] , set the high index to mid-1 ; if key == list[mid] , a match is found and return mid ; if key > list[mid] , set the low index to mid+1 . Continue the search until low > high or a match is found. If low > high , return “1 “ low , where low is the insertion point.
What happens if (high >= low) in line 7 is replaced by (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 in the list. The method returns the index of one of the matching elements if the element is in the list.
Please trace the program using the following statements:
int [] list = { 2 , 4 , 7 , 10 , 11 , 45 , 50 , 59 , 60 , 66 , 69 , 70 , 79 }; int i = binarySearch(list, 2 ); // returns 0 int j = binarySearch(list, 11 ); // returns 4 int k = binarySearch(list, 12 ); // returns 6
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 requires that the array be pre-sorted. |
EAN: N/A
Pages: 503