Binary Search & Parametric Search

[Binary Search]

이진 탐색은 오름차순으로 정렬된 배열을 기반으로 원하는 값을 찾을 때 사용하는 탐색 방법 중 하나이다.

만약 1부터 10까지 정렬된 배열에서 3을 찾고 싶다면, 가운데 mid값을 기준으로 mid값보다 3이 작다면 왼쪽 영역에서, 크다면 오른쪽 영역에서 3을 찾는다. 해당역역에서 다시 가운데 mid값을 찾아서 3과 비교해 영역을 나눠가며 비교의 범위를 절반씩 줄여 나갈 수 있게 된다. 한번 비교할 때마다 범위가 절반씩 줄어들기 때문에 시간복잡도가 O(logN)이다.

[구현]

<반복>

class BinarySearch
{
	public static void main (String[] args)
	{
		int[] arr = {1,2,3,4,5,6,7,8,9,10};
 
		System.out.println(bSearch(arr, 10, 3));
	}
 
	public static int bSearch(int[] arr, int size, int value)
	{
		int left = 0;
		int right = size - 1;
		int mid;
 
		while(left < right)
		{
			mid = (left+right)/2;
 
			if(arr[mid] == value)
				return mid;
			else if(arr[mid] > value)
				right = mid - 1;
			else 
				left = mid + 1;
		}
 
		return -1;
	}
}

값이 존재하면 그 인덱스를 반환하고, 존재하지 않다면 -1을 반환한다. 

[Parametric Search]

기본적인 탐색 방법은 Binary Search와 비슷하다. 대신 값을 바로 구해내는 것이 아니고, 임의의 값을 던지고 맞는지 확인해가며 해를 구하는 방법이다. 

-> 해가 존재할 수 있는 연속된 구간에서 임의의 답 k를 정해서 k가 가능한지의 여부를 판단하여 k의 범위를 줄임으로써 최적해를 구하는 방법

초기값으로 해의 최솟값과 최댓값을 이진탐색의 low, high 값으로 각각 지정한다. 

mid((low+high)/2) 값이 해가 될 수 있는지 검사한다. -> 가능한지에 대한 여부는 원래 이진 검색에서는 단순히 mid값과 같은지만 확인하면 됬었지만, 파라메트릭 탐색에서는 내가 원하는 조건에 만족해야 하므로 그 조건은 문제에 따라 다르다. 

mid값으로 해결된다면 high값을 mid값으로 만들어서 범위를 좁혀가고, 반대라면 low값에 mid값을 넣어주어 범위를 좁혀간다. 

{
	  answer = -INF;
	  while (start <= end) {
	      int mid = (start + end) / 2;
	      if (possible(mid)) {
	          end = mid - 1;
	          answer = max(answer, mid);
	      }
	      else 
	          start = mid + 1;
	  }
	  return answer;
}

[참고]

http://coderkoo.tistory.com/8