2.정렬된 수에서 하나의 수의 위치 찾기

문제정의

- 여러 개의 수가 정렬된 순서로 있을 때 특정한 수를 찾는 방법

- 단순 반복문을 이용하면 수의 개수에 따라 비교 횟수가 증가하는 O(n)의 수행이 이루어짐

- 수가 정렬된 상태에서는 이진 탐색(binary search)을 활용하면 매번 비교되는 요소의 수가 절반을 감소될 수 있으므로 O(longN)의 수행으로 원하는 수를 찾을 수 있음

- 수의 예 : [12,25,31,48,54,66,70,83,95,108]

- 83의 위치를 찾아보세요

- 88의 위치를 찾아보세요

 

해결방법

- 수가 정렬된 상태이므로 중간의 값을 하나 선택한다. 찾으려는 값이 그보다 크면 범위를 오른쪽으로 그보다 작으면 범위를 왼쪽으로 좁힐 수 있다.

- 한번 비교할 때마다 1/2씩 범위가 좁혀진다.

 

코딩

- BinarySearchProblem.java

public class BinarySearchProblem {

public static void main(String[] args) {

int [] arr = {12,25,31,48,54,66,70,83,95,108};

int target = 83;

int left = 0;
int right = arr.length-1;
int mid = (left+right)/2;

int temp = arr[mid];
boolean find =false;

while(left <= right) {
if(target == temp) {
find = true;
break;
}
else if(target < temp) {
right = mid-1;
}
else {
left = mid+1;
}
mid = (left + right)/2;
temp = arr[mid];
}

if(find == true)
{
mid++;
System.out.println("찾는 수는 " + mid +"번째 있습니다.");
}
else System.out.println("찾는 수가 없습니다.");

}

}