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 */ }

 이전페이지 / 3 / 다음페이지