이진 탐색의 변형

1.문제

[이진 탐색의 변형 (A Variation of Binary Search)]
크기가 매우 큰 정수 배열 a[veryLarge]에 서로 다른 임의의 양의 원소값 a₁, a₂, ... 이 저장되어 있다. 단, 저장된 원소의 개수는 현재 알 수 없으며 원소값들은 a₁< a₂< ...의 조건을 만족한다고 가정한다. 어떤 key값 x가 주어졌을 때 x값의 위치(배열의 인덱스)를 반환하는 함수를 작성하라.
(제한 조건 : x와 원소의 비교 횟수는 원소의 개수(n)에 대한 어떤 함수에 비례해야지 배열의 크기(veryLarge)에 비례해서는 안된다.
입력 : 배열 a와 key값 x
출력 : x의 위치(x가 a에 존재하지 않을 경우는 -1)
< 주의 사항 >
1. veryLarge(배열의 크기)값은 사용하는 컴퓨터에서 최대로 가능한 큰 값으로 한다.

2. 배열에서 원소값이 들어가 있지 않은 곳의 값은 0으로 가정한다.

3. 원소의 개수를 모르므로 프로그램에서 탐색할 때 원소의 개수를 이용해서는 안된다.

4. 각 테스트 자료에 대해 결과를 출력할 때 배열의 원소값은 a[i] = 2*i-1(단, 1 ≤ i ≤원소개수)로 저장하여 사용한다.(각 테스트 자료에 대해 원소의 개수는 달라야 함)

2.알고리즘

① 키값과 사이즈을 입력받는다.

② 탐색할 범위를 정한다.

③ binsearch를 실행한다.

④ 결과를 출력한다.

3.프로그램을 짜본 후...
verylarge값을 2000000000으로 했더니 컴퓨터에 메모리가 부족하다고 실행이 안됐다.
그후로는 값을 아무리 줄여도 계속 실행이 되지 않아서 컴퓨터를 재부팅해야 했다.--;;
(100으로 해도 안되었다.)
4.SOURCE CODE
…