이진 탐색의 변형
페이지 정보
작성일 22-12-04 08:05
본문
Download : 이진 탐색의 변형.hwp
③ binsearch를 실행한다.
1.문제
[이진 탐색의 변형 (A Variation of Binary Search)]
크기가 매우 큰 정수 배열 a[veryLarge]에 서로 다른 임의의 양의 원소값 a₁, a₂, ... 이 저장되어 있다아 단, 저장된 원소의 개수는 현재 알 수 없으며 원소값들은 a₁< a₂< ...의 조건을 만족한다고 가정한다.
그후로는 값을 아무리 줄여도 계속 실행이 되지 않아서 컴퓨터를 재부팅해야 했다.
Download : 이진 탐색의 변형.hwp( 36 )
이진탐색의변형
이진 탐색의 변형에 대한 자료입니다. 이진탐색의변형 , 이진 탐색의 변형기타레포트 ,
,기타,레포트
레포트/기타
설명
순서
이진 탐색의 변형
이진 탐색의 변형에 대한 입니다.
2. 배열에서 원소값이 들어가 있지 않은 곳의 값은 0으로 가정한다.)
4.SOURCE CODE
#include
#define verylarge 2000000 //매우 큰 값을 verylarge로 잡는다.
3. 원소의 개수를 모르므로 호로그램에서 탐색할 때 원소의 개수를 이용해서는 안된다된다.
입력 : 배열 a와 key값 x
출력 : x의 위치(x가 a에 존재하지 않을 경우는 -1)
< 주의 사항 >
1. veryLarge(배열의 크기)값은 사용하는 컴퓨터에서 최대로 가능한 큰 값으로 한다.
…(skip)
다.
3.호로그램을 짜본 후...
verylarge값을 2000000000으로 했더니 컴퓨터에 메모리가 부족하다고 실행이 안됐다. 어떤 key값 x가 주어졌을 때 x값의 위치(배열의 인덱스)를 반환하는 함수를 작성하라.
(제한 조건 : x와 원소의 비교 횟수는 원소의 개수(n)에 대한 어떤 함수에 비례해야지 배열의 크기(veryLarge)에 비례해서는 안된다된다.(각 테스트 data(資料)에 대해 원소의 개수는 달라야 함)
2.알고리즘
① 키값과 사이즈을 입력받는다.
② 탐색할 범위를 정한다.
④ 결과를 출력한다.
4. 각 테스트 data(資料)에 대해 결과를 출력할 때 배열의 원소값은 a[i] = 2*i-1(단, 1 ≤ i ≤원introduction수)로 저장하여 사용한다.--;;
(100으로 해도 안되었다.
