AP Computer Science :: Lessons :: Search Methods
Chapter 5:
Pages 271 - 272
Chapter 12
Pages 524 - 540
Fundamentals of Java
Chapter 11
Pages 411 - 415
Chapter 12
Pages 468 - 478
Searching
There are two main ways to search an array or list for a given value. A sequential search starts at the first element and compares it to a given value until that value is found or it reaches the end of an array. This search works better with an array that is already sorted. A binary search only works for a sorted array and uses a divide-and-conquer approach to work more efficiently. Binary search looks at an element in the middle of the array and, depending on the outcome, chooses the next half of the array to search. The code for each type of search in Java is below.
int seqSearch(int[] a, int value)
{
for (int i=0; i<a.length; i++)
if (a[i] == value)
return i;
return -1;
}
int binSearch(int[] a, int value, int left, int right)
{
if (left > right)
return -1;
else
{
int midpoint = (left + right) / 2;
if (a[midpoint] == value)
return midpoint;
else if (a[midpoint] < value)
return binSearch(a, value, midpoint+1, right);
else
return binSearch(a, value, left, midpoint-1);
}
}
Sequential searches have an average runtime of O(n) while binary searches have an average of O(log n). The following is a comparison of sequential search and binary search:
| Sequential Search | Binary Search |
|---|---|
| Sequential algorithm | Divide-and-conquer algorithm |
| Works on any array | Array MUST be sorted |
| Average Runtime: O(n) | Average Runtime: O(log n) |
