[알고리즘]Binary Search - 이분검색

8. 이분검색
N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면, 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램

입력) 첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다.
두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.
출력) 첫 줄에 정렬 후 M의 값의 위치 번호를 출력합니다.

 

 

*이진 검색 알고리즘(binary search algorithm) : 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘

- 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식

- 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다

- 시간복잡도 : O(logN) ...?

 

 

import java.util.Arrays;
import java.util.Scanner;

public class Main { // binary search
	
	public static int solution(int n, int m, int[] arr) {
		int answer = 0;
		
		Arrays.sort(arr); // 오름차순 정렬
		int lt = 0, rt = n-1; 		
		while(lt<=rt) {
			int mid = (lt+rt)/2;
			if (arr[mid]==m) {
				answer = mid+1;
				break;
			} 
			if (arr[mid]>m) rt = mid-1;
			else lt = mid+1;
		}
		return answer;
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt(); // 배열 크기
		int m = scanner.nextInt(); // 찾는 숫자
		int[] arr = new int[n];
		for (int i=0; i<n; i++) {
			arr[i] = scanner.nextInt();
		}
		System.out.println(solution(n,m,arr));
	}

}

---

결과

입력
8 32
23 87 65 12 57 32 99 81

출력
3