| |
2. Search
|
| |
| 2.1 Sequential Search |
| |
 One way to search for a record with the specified key is to examine the list of records in left-to-right or right-to-left order.
Analysis: O(n) |
| |
// return the least i such that list[i] = x;
// return -1, if x is not found
int seqseach(int list[], int x, int n)
{
int i;
for (i=1; i<=n && list[i]!=x; i++) ;
if (i>n) return -1; /* not found */
return i;
}
|
|
| |
| 2.2 Binary Search |
| |
One way to search for a record with the specified key in an ordered, sequential list
Analysis: O(log n) |
| |
// find x in list[0] <= list[1] <= ... <= list[n-1]
int binsearch(int list[], int x, int n)
{
int min, max, mid;
min = 0;
max = n - 1;
while (min <= max) {
mid = (min+max)/2;
if (x < list[mid])
max = mid - 1;
else if (x > list[mid])
min = mid + 1;
else
return mid; /* found match */
}
return -1; /* not found */
} |
|
|
|
|