섹션 6. Sorting and Searching(정렬, 이분검색과 결정알고리즘) 8. 이분검색

문제

• 임의의 N개의 숫자가 입력으로 주어집니다. 
• N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. 
• 단 중복값은 존재하지 않습니다.

입력

• 첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다.
• 두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.

출력

• 첫 줄에 정렬 후 M의 값의 위치 번호를 출력한다.

입출력 예제

---

풀이방식

이번 문제는 이분검색를(을) 사용하여 푸는 문제이다.

---

이분검색이란 정렬된 데이터를 가지고 자료를 반으로 나누어 검색하는 방식이다.

찾고 싶은 데이터(키 값), 시작 위치에 대한 값, 종료 위치에 대한 값, 중간 위치에 대한 값이 필요하다.

중간 위치의 값을 키 값과 비교하여 같다면 검색 종료, 작다면 왼쪽 데이터를 다시 검사하고 크다면 오른쪽 데이터를 다시 검사한다.

---

설계과정

1. 배열을 복사하여 새로운 배열을 만든다.

2. 기존 배열과 복사한 배열을 비교하여 값이 다른 번호를 출력한다.

---

풀이과정

1. 값들을 입력받는 코드를 작성한다.

 

2. int 형으로 메소드를 작성한다.

 

3. 배열을 오름차순으로 정렬하고, lt와 rt 값을 각각 초기화한다.

• Arrays.sort() : 배열을 오름차순으로 정렬한다.
• lt : 왼쪽부터 오른쪽으로 진행하는 인덱스이다.
• rt : 오른쪽부터 왼쪽으로 진행하는 인덱스이다.
• rt는 N-1을 통해 맨 마지막 인덱스를 가리키도록 한다.

4. lt 가 rt보다 작거나 같을 때 도는 while 문을 작성한다.

• lt가 rt보다 크다는 것은 탐색하는 값이 맨 끝 인덱스를 넘었다는 것이므로 검색할 자료가 끝났음을 의미한다.

5. 중간 인덱스인 mid을 선언하고, 찾고자 하는 M 값이 mid 인덱스에 있으면 1을 더해서 결과를 출력한다.

• 인덱스는 0부터 시작하므로 1을 더해야 번호가 출력된다.
• 더 탐색할 필요가 없으므로 break; 한다.

5. mid 번째 값이 M 보다 크면 왼쪽인 맨 마지막 값(rt)에 1을 뺀다.

• 이를 통해 그 뒤의 값은 탐색하는 범위에서 제외시킨다.
• 즉, 탐색 범위을 mid - 1 번째까지만 진행한다는 의미이다.

5. mid 번째 값이 M 보다 작으면 오른쪽인 초기 값(lt)에 1을 더한다.

• 탐색 범위를 mid + 1 번째부터 진행한다는 의미이다.

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.