Embedded Files
Linear Search
The linear search checks each element of the array from the zero index through length – 1. If an element matches the search value, then the linear search method will return the index where the matching value exists. If there is no matching value, then it will return -1, since array indices cannot be negative this is a clear indicator that the search value was not found in the array.
For example, in the array [3 11 7 10 6 2 15], if the searchValue = 6, the linear search method would return 4. However, if the searchValue = 5, the linear search method would return -1, because there is no 5 in this array.
linearSearchMethod Code for int[] arrays
int search(int[] a, int searchValue)
{
for(int i = 0; i < a.length; i++)
if(a[i] == searchValue)
return i;
return -1;
}
linearSearchMethod Code for String[ ] arrays
int search(String[] a, String searchValue)
{
for(int i = 0; i < a.length; i++)
if(a[i].equals(searchValue))
return i;
return -1;
}
The linearSearchMethod is not an efficient method, so it is only recommended for arrays with a few hundred elements. Once arrays become large (thousands or even millions of entries) then it becomes necessary to keep your arrays sorted so that more efficient search methods can be implemented.
Binary Search
The Binary Search Method is a much more efficient way to search arrays, however it requires that the array be sorted before searching. The binarySearchMethod examines the value at the midpoint of the indices, and cuts the search interval down by half for each iteration such that the midpoint does not match the search value.
Example(1): arr = [“A”,“C”,“E”,“G”,“J”,“L”,“M”,“P”,“Q”,“S”,“W”,“X”,“Z”]
arr.length = 13 therefore the left index = 0 and the right index = 12. Midpoint of 0 & 12 = 6.
If searchValue = “Q”, then the following is a trace of how the binarySearchMethod would execute.
Trace of binarySearchMethod that finds the targeted searchValue
1st iteration: Midpoint of left and right indices = (0 + 12) / 2 --> midpoint = 6.
arr[6] = “M” which is not equal to “Q”
However, since “M” < “Q” the new left index is equal to 6 + 1. Left index = 7
2nd iteration: Midpoint of left and right indices = (7 + 12) / 2 --> midpoint = 9. (integer math)
arr[9] = “S” which is not equal to “Q”
However, since “S” > “Q” the new right index is equal to 9 – 1. Right index = 8
3rd iteration: Midpoint of left and right indices = (7 + 8) / 2 --> midpoint = 7. (integer math)
arr[7] = “P” which is not equal to “Q”
However, since “P” < “Q” the new right index is equal to 7 + 1. Left index = 8
4th iteration: Midpoint of left and right indices = (8 + 8) / 2 --> midpoint = 8.
arr[8] = “Q” which is not equal to “Q”
Since “Q”.equals( “Q”) is true, the binarySearchMethod will return 8.
Example (2): arr = [“A”,“C”,“E”,“G”,“J”,“L”,“M”,“P”,“Q”,“S”,“W”,“X”,“Z”]
If searchValue = “D”, then the following is a trace of how the binarySearchMethod would execute.
Trace of binarySearchMethod that doesn’t find the targeted searchValue
1st iteration: While(right index – left index) > 0 --> (12 – 0) ≥ 0 Continue search.
Midpoint of left and right indices = (0 + 12) / 2 --> midpoint = 6.
arr[6] = “M” which is not equal to “D”
However, since “M” > “Q” the new right index is equal to 6 - 1. Right index = 5
2nd iteration: While(right index – left index) > 0 --> (5 – 0) ≥ 0 Continue search.
Midpoint of left and right indices = (0 + 5) / 2 --> midpoint = 2. (integer math)
arr[2] = “E” which is not equal to “D”
However, since “E” > “D” the new right index is equal to 2 – 1. Right index = 1
3rd iteration: While(right index – left index) > 0 --> (1 – 0) ≥ 0 Continue search.
Midpoint of left and right indices = (0 + 1) / 2 --> midpoint = 0. (integer math)
arr[0] = “A” which is not equal to “D”
However, since “A” < “D” the new left index is equal to 0 + 1. Left index = 1
4rd iteration: While(right index – left index) > 0 --> (1 – 1) ≥ 0 Continue search.
Midpoint of left and right indices = (1 + 1) / 2 --> midpoint = 1.
arr[1] = “C” which is not equal to “D”
However, since “C” < “D” the new left index is equal to 1 + 1. Left index = 2
4th iteration: Now (right index – left index) < 0. --> (1 – 2) < 0 Stop search! searchValue not found!
binarySearchMethod Code for int[ ] arrays
int search(int[] a, int searchValue)
{
int left = 0; //Establish left index
int right = a.length - 1; //Establish right index
while(left <= right) //Loop until right-left < 0
{
int midpoint=(left+right)/2; //Compute current midpoint
if(a[midpoint]==searchValue) //Target found; return index
return midpoint;
else if(a[midpoint]<searchValue) //Target right of midpoint
left = midpoint + 1;
else //Target left of midpoint
right = midpoint - 1;
}
return - 1; //Target not found
}
binarySearchMethod Code for String[ ] arrays
int search(String[] a, String target)
{
int left = 0; //Establish left index
int right = a.length - 1; //Establish right index
while(left <= right) //Loop until right-left < 0
{
int mid = (left+right)/2; //Compute current midpoint
int result=(a[mid].compareTo(target)); //lexicographic comparison
if(result == 0) //Target found; return index
return mid;
else if(result < 0) //Target right of midpoint
left = mid + 1;
else //Target left of midpoint
right = mid -1;
}
return -1; //Target not found
}
Page updated
Google Sites
Report abuse