Home

Published

- 8 min read

[ Algorithm ] 이진탐색(Binary Search)

Computer Science Algorithm
img of [ Algorithm ] 이진탐색(Binary Search)

이진 탐색은 정렬된 배열(sorted array)에서 특정 값을 찾는 효율적인 알고리즘(algorithm)이다. 이 알고리즘은 ‘분할 정복(divide and conquer)’ 방식을 사용하여 탐색 범위를 반으로 줄여가며 원하는 값을 찾는다.

이진 탐색의 작동 원리

  1. 배열의 중간 요소를 선택한다.
  2. 중간 요소와 찾고자 하는 값을 비교한다.
  3. 찾고자 하는 값이 중간 요소보다 작으면 왼쪽 절반을, 크면 오른쪽 절반을 선택한다.
  4. 선택된 절반에 대해 1-3 과정을 반복한다.
  5. 찾고자 하는 값을 찾거나, 더 이상 탐색할 범위가 없을 때까지 반복한다.
  • 가운데 위치를 확인
  • 가운데 값과 찾으려는 값을 비교
  • 다시 가운데 위치를 확인
  • 비교 후 다시 정함

이진 탐색의 구현

   def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1  # 타겟을 찾지 못한 경우

시간 복잡도(Time Complexity)

  • 최악의 경우(Worst case): O(log n)
  • 평균의 경우(Average case): O(log n)
  • 최선의 경우(Best case): O(1)

이진 탐색의 시간 복잡도가 O(log n)인 이유는 매 단계마다 탐색 범위가 절반으로 줄어들기 때문이다.

이진 탐색의 장단점

장점(Advantages):

  • 대규모 정렬된 데이터에서 매우 효율적이다.
  • 선형 탐색(linear search)에 비해 훨씬 빠르다.

단점(Disadvantages):

  • 데이터가 정렬되어 있어야 한다.
  • 랜덤 접근(random access)이 가능한 자료구조(예: 배열)에서만 사용 가능하다.

재귀함수의 경우

  • JAVA
   public static int binarySearchRecursive(int nums[], int l, int r, int value){
	if(l > r){
		return -1;
	}
	int m = (l + r) / 2;
	if(nums[m] == value){
		return m;
	}
	if(nums[m] < value){
		return binarySearchRecursive(nums, m + 1, r, value);
	}
	if(nums[m] > value){
		return binarySearchRecursive(nums, l, m - 1, value);
	}
	return -1;
}
  • C
   /*
	- `a[]`: 정렬된 배열
	- `n`: 배열의 크기
	- `x`: 찾고자 하는 값
*/
int search(int a[], int n, int x){
	if (n==0) return -1;
	m = n / 2;
	if (x==a[m]) return m;
	else if (x<a[m]) return search(a, m, x);
	else {
		r = search(a + m + 1, n - m - 1, x);
		if (r==-1) return -1;
		else return r + m + 1;
	}
}

// C 스타일의 수도 코드
int search(int a[], int n, int x){
	if (n == 0) return -1;
	m = n / 2;
	if (x==a[m]) return 1;
	else if (x<a[m]) return search(a, m , x);
	else { return search(a + m + 1, n - m - 1, x);
	}

}

재귀함수가 아닌 경우

  • C
   int search(int a[], int n, int x) {
	int l, r, m;
	l = 0; r = n - 1;
	while (l <= r) {
		m = (l + r) / 2
		if(a[m] < x)
			l = m + 1;
		else if (a[m] < x)
			r = m - 1;
		else // same
			return m;
	}
	return -1;
}

/*
- r-l 이 계속 줄어든다.
- 그러므로 프로그램은 끝난다.
*/

정렬된 데이터와 알고리즘

정렬된 데이터(sorted data)는 많은 효율적인 알고리즘을 적용할 수 있는 장점이 있다

  • 어떤 값의 위치 찾기: O(log n)의 시간 복잡도(time complexity)
  • 최솟값/최댓값 찾기: O(1)의 시간 복잡도

정렬되지 않은 배열(unsorted array)의 경우

  • 정렬 알고리즘(sorting algorithm)을 사용하여 정렬 가능
  • 정렬 후에는 효율적인 알고리즘 사용 가능
  • 단, 새 요소 추가 시 재정렬 필요
    • 이는 때때로 비효율적일 수 있음(배보다 배꼽이 더 커질 수 있음)
    • 정렬 알고리즘의 시간 복잡도가 이진 탐색(binary search) 알고리즘보다 높음

정렬 후 이진탐색 vs 선형 탐색

배열이 안 바뀌는 경우배열이 바뀌는 경우
• 탐색할 일이 많은 경우
▸ 정렬 한 번 후, 이진 탐색 여러 번
▸ O(정렬) + O(log n) × x		• 요소를 삽입하는 경우만 문제
• 보통 선형 탐색을 사용
• 이진 탐색을 사용하려면?
▸ 탐색 전에 배열을 정렬해야 함
• 배열이 바뀔 때마다 곧바로
• 배열이 바뀐 적이 있다면 탐색 직전에
▸ 선형 탐색보다 느릴 수 있음
• 탐색과 배열 변경 빈도에 따라
• 탐색 빈도가 높을수록 유리
• 탐색을 한 번만 할 경우
▸ 선형 탐색
▸ O(n)

배열이 안 바뀌는 경우

  • 탐색할 일이 많은 경우
    • 정렬 한 번 후, 이진 탐색 여러 번
    • 시간 복잡도: O(정렬) + O(log n) × x (x는 탐색 횟수)
  • 탐색을 한 번만 할 경우
    • 선형 탐색(linear search) 사용
    • 시간 복잡도: O(n)

배열이 바뀌는 경우

  • 요소를 삽입하는 경우에만 문제가 됨
  • 보통 선형 탐색을 사용
  • 이진 탐색을 사용하려면:
    • 탐색 전에 배열을 정렬해야 함 • 배열이 바뀔 때마다 곧바로 • 배열이 바뀐 적이 있다면 탐색 직전에
    • 선형 탐색보다 느릴 수 있음 • 탐색과 배열 변경 빈도에 따라 다름 • 탐색 빈도가 높을수록 이진 탐색이 유리

데이터의 특성, 변경 빈도, 탐색 빈도 등을 고려하여 최적의 접근 방식을 선택해야 한다. 정렬된 데이터의 이점은 분명하지만, 데이터 변경이 빈번한 경우 정렬 유지에 따른 오버헤드(overhead)를 신중히 고려해야 한다.

회전된 배열에서의 검색

   public class Program{
	public static void main(String[] args){
		int[] arry = new int[]{20, 25, 26, 29, 33, 1, 3, 5, 6, 10, 11, 19};

		int index = indexOfRotatedArray(arry, 0, arry.length - 1, 0);

	}


	private static int indexOfRotatedArray(int[] arry, int start, int end, int num){
		if(start > end){
			return -1;
		}

		int mid = (start + end) / 2;
		if(arry[mid] == num){
			return mid;
		}
		// start부터 mid까지 있는 숫자들이 정렬된 경우
		if(arry[start] <= arry[mid]){
			// num이 start와 mid 사이에 있는 경우
			if(num >= arry[start] && num <= arry[mid]){
				return indexOfRotatedArray(arry, start, mid -1, num);
			}
			return indexOfRotatedArray(arry, mid + 1, end, num);
		}
		// mid부터 end까지에 있는 숫자들이 정렬된 경우 && 그 사이에 num이 있는 경우
		if(num >= arry[mid] && num <= arry[end]) {
			return indexOfRotatedArrary(arry, mid + 1, end, num);
		}
		return indexOfRotatedArrary(arry, start, mid - 1, num);
	}
}