개발 공부 - [컴퓨터과학] 알고리즘 - 이진 검색

앞에 알고리즘에서 [추측 게임] 을 단계별로 나타내 보면,

1. min = 1 , max = n 으로 둔다.

2. max와 min의 평균을 구하되, 정수가 되도록 내림한다.

3. 추측이 맞으면 끝낸다 (숫자를 찾았다.)

4. 추측값이 너무 작으면 min을 추측값보다 1 크게 설정한다.

5. 추측값이 너무 크면 max를 1 작게 설정한다.

6. 다시 2단계로 돌아간다.

 이걸 수도 코드로 표현해 보면

1. min = 0 이고 max = n-1이라고 한다.

2. guess 의 값은 max와 min의 평균값을 정수가 되도록 버림한 값이다.

3. array[guess]의 값이 target과 같다면 검색을 멈춘다. (타겟을 찾았다 -> guess를 결과값으로 반환한다.)

4. 추측값이 더 작을 경우 (array[guess] < target) 에는 min = guess+1로 바꾼다.

5. 아니면 추측값이 더 클 경우에는 max = guess -1 로 바꾼다.

6. 다시 2단계로 돌아간다.

1. 32개 팀이 2014 월드컵에 진출하게 되었습니다. 팀명들을 (배열로) 정렬한다고 할 때, 최악의 경우에서 이진 검색을 활용해 배열 내에서 특정 팀을 찾아내고자하면 몇 개의 항목을 확인해야 할까요?

-> 2^6 이니까 6 

2. 밑이 2인 32의 로그인 \log(32)log(32)log, left parenthesis, 32, right parenthesis는 무엇일까요?

-> 2^5 = 5

3.2에서 311까지 소수를 정렬한 배열이 있습니다: [2, 3, 5, 7, 11, 13..., 307, 311]. 항목의 수는 64개이며, 이진 검색에서 52가 배열에 없으므로 소수가 아니다는 결론을 내릴 때까지 얼마나 많은 항목을 확인해야 할까요?

-> 7

4.2013년 유엔 회원국의 수는 193개국 이었습니다. 이 국가명들은 알파벳 순으로 배열내에서 정렬한다면, 이진 검색을 활용하여 특정한 국가명을 찾을 때까지 최악의 경우 몇 개의 국가명을 확인해야 할까요?

-> 8

5. 2014년 "Catalogue of Life"에는 약 1580000종의 이름이 등재되어 있습니다. 이 이름들을 배열 안에서 정렬한다면, 이진 검색을 활용하여 특정한 종의 이름을 찾을 때까지는 최악의 경우 몇 개의 이름을 확인해야 할까요 ?

-> 21 (22아녀?)