array searching

크기가 무한한 array에서, 처음 n개에는 정수들이 sort되어 들어있고, 나머지는 아주 큰 숫자 (무한대)로 채워져 있다. 어떤 숫자 x가 주어졌을 때, 이러한 array에서 x의 위치를 찾는 방법은? n의 값은 모른다고 가정한다.

실수 data[무한대]; // 실수 배열 data에 무한대 개의 자료가 들어 있다.

low=1; // 배열의 인덱스가 1로 부터 출발하는 것으로 보았다. 0 부터 출발한다면 고치면 된다.

mid=2; // 이분 검색 방법을 역으로 돌린 것이다.

high=3; // 구간을 3배씩 확장해 가면서 x가 포함되어 있는 구간을 찾는다.

while (data[high] < x) {

  low=high;

  mid=high+high;

  high=mid+high;

}

while 문이 끝날수 밖에 없다.

이때는 data[low] <= x <= data[high] 를 만족한다.

이때 우리는 구간 low, high를 알고 있다. 이 사이에 x가 들어있는 것이다.

여기서 부터 이분검색을 하여 찾아 나가면된다.

while (low<high) {

  if (data[mid]==x) { 찾았다. break;}

  if (data[mid] > x) {

    high=mid;

    mid=(low+high)/2;

  }

  else {

    low=mid;

    mid=(low+high)/2;

  }

}

이 while문이 끝나면 x가 없기 때문에 찾지 못하던지 아니면 찾을수 있다.