Chapter 1-5 Searching an Ordered Array

1）ナビゲーションアルゴリズムA

- Input data and Data structure : unsorted array
- sequential search

int seqSearch(int[] E, int n, int K)
    int ans, index;
    ans = -1; // Assume failure
    for(index = 0; index < n; index++)
    	if(K == E[index])
           ans = index; // Success!
           break; // Done!
    return ans;

- W(n) = n 
- A(n) = q[(n+1)/2] + (1-q)n
	(K가 array의 마지막이거나, 존재하지 않을 때 평균 수행시간)

- F(n) = n이므로 Algorithm A는 Optimal 하다.

2）ナビゲーションアルゴリズムB

- Input data and Data structure : 오름차순으로 정렬된 Array
- sequential search

- int seqSearch(int[] E, int n, int K) 
  A와 동일

- W(n) = n 
- A(n) = q[(n+1)/2] + (1-q)n
  A와 알고리즘이 같으므로 분석내용 또한 같다

 정렬되었음을 그닥 활용하지 않아 효율성은 없다.

3）ナビゲーションアルゴリズムC

- Input data and Data structure : 오름차순으로 정렬된 Array
- sequential search : 
  entry에서 K보다 큰 값을 만나면 알고리즘을 종료한다.

int seqSearchMod(int[] E, int n, int K) 
  int ans, index;
  ans = -1; // Assume failure
  for(index = 0; index < n; index++)
  	if(K>E[index]) continue;
    	if(K<E[index]) break; //Done!
    	//K==E[index]
        ans = index; //Find it
        break;
  return ans;

Analysis C

4）ナビゲーションアルゴリズムD：Binary Search

- K값을 array의 중간값과 비교한다
- 한번의 비교에 entry의 나머지 절반을 제거한다.
- 같은 전략을 재귀적으로 반복한다.

- Input : first, last (살펴볼 index의 처음과 끝), K, 
정렬된 배열 내에서 index 값이 first와 last 사이에 있는 모든 정수
- Output : K가 존재하는 index값, 혹은 E안에 K가 없을 때 나오는 결과 -1
- 반드시 정렬 된 array에서만 사용한다.

int binarySearch(int[] E, int first, int last, int K)
    if(last < first) // base case
    	index = -1;   // 재귀문을 탈출할 수 있도록 하는 조건
    else
    	int mid = (first + last) / 2;
        if (K == E[mid]) index = mid;
        else if(K < E[mid]) index = binarySearch(E, first, mid-1, K)
        else index = binarySearch(E, mid+1, last, K)
    return index

Average-Behavior Analysis of Binary Search