[알고리즘] 이분 탐색 (Binary Search)

이분 탐색 (Binary Search)

• O( log N )의 시간 복잡도로 전체 배열에서 특정 값을 찾아내는 방법
• 이 때 배열은 무조건 정렬이 되어있어야함
• 반복문 실행할 때마다 탐색 범위를 왼쪽 절반 혹은 오른쪽 절반으로 줄여 나감

 

응용

• 최대값, 혹은 최소값을 찾는 문제

1939번: 중량제한

 

알고리즘

1. left = index 최소 값
2. right = index 최대 값
3. 반복문 실행
   1. left가 right 보다 이하일 동안 반복 (left <= right)
   2. mid = left와 right의 중간 값
   3. key 값 == mid 값 → 반복문 종료
   4. key 값 < mid 값 → 탐색 범위를 mid 기준 왼쪽 절반으로 줄임 → right = mid - 1
   5. key 값 > mid 값 → 탐색 범위를 mid 기준 오른쪽 절반으로 줄임 → left = mid + 1

 

//list 안에 a가 존재하는지 확인
	static boolean binarySearch(int[] list, int a)
	{
		//나올 수 있는 최소 index
		int left = 0;

		//나올 수 있는 최대 index
		int right = list.length-1;

		while(left <= right)
		{
			int mid = (left + right) / 2;

			if(list[mid] == a)
				return true;
			else if(list[mid] > a)
				right = mid - 1;
			else
				left = mid + 1;
		}

		return false;
	}