Cs/알고리즘&자료구조

이분탐색(Binary Search)

ukkkk7 2023. 12. 3. 00:01
728x90
반응형

 

 

 

이진 탐색(Binary Search) 이란?

 

'정렬된 배열'에서 '특정 값'을 찾는 알고리즘이다.

- 전체를 순회하며 탐색하는 선형탐색에 비해 빠른 속도를 보장하지만 배열이 정렬되어 있어야 한다는 조건이 필요하기 때문에 배열이 정렬되어 있지 않은 경우 정렬 작업이 필요하다.

 

위의 모션은 '이진탐색'의 탐색 과정과 '선형탐색'의 과정을 보여주고 있다.

 

이진탐색 과정

  1. 배열의 중간 값을 선택하여 찾고자 하는 값과 비교한다. 
  2. 만약 중간 값이 찾고자 하는 값보다 크면 배열 왼쪽 부분에서 다시 탐색을 진행하고 중간값이 작다면 배열 오른쪽 부분에서 탐색을 진행한다.
  3. 해당 과정을 찾고자 하는 값이 나올때까지 반복한다.

 

이진 탐색의 구현 방법에는 재귀를 통한 구현과 반복을 통한 구현 방법이 있다.

 

기본적인 구현 과정

1. 탐색의 대상이 되는 자료들이 arr[low]부터 arr[high]에 들어있다고 가정해보자(배열은 정렬된 상태여야 한다)

- 즉 탐색해야 할 범위는 low - 0번 인덱스 부터  high - n-1번 인덱스 까지이다.

 

2. mid값은 (low + high) / 2이다.

 

3. arr[mid]값과 구하고자 하는 key값을 비교한다.

3-1. 구하는 값 > mid : 찾는 값이 중간값 보다 높다면 low를 mid + 1로 만들어준다.

3-2. 구하는 값 < mid : 찾는 값이 중간값 보다 작다면 high를 mid -1 로 만들어준다.

3-3. 구하는 값 == mid : 값을 찾으면 중간값을 리턴

 

4. low  <=  high 까지 반복하면서 값을 찾는다 -> high가 low보다 작아진다면 모든 범위를 탐색한 것이기 때문

 

 

 

재귀를 이용한 이진 탐색

int binarySearch1(int key, int low, int high) {
	int mid;

	if(low <= high) {
		mid = (low + high) / 2;

		if(key == arr[mid]) { // 탐색 성공 
			return mid;
		} else if(key < arr[mid]) {
			// 왼쪽 부분 arr[0]부터 arr[mid-1]에서의 탐색 
			return binarySearch1(key ,low, mid-1);  
		} else {
			// 오른쪽 부분 - arr[mid+1]부터 arr[high]에서의 탐색 
			return binarySearch1(key, mid+1, high); 
		}
	}

	return -1; // 탐색 실패 
}

 

 

반복을 이용한 이진 탐색

int binarySearch2(int key, int low, int high) {
	int mid;

	while(low <= high) {
		mid = (low + high) / 2;

		if(key == arr[mid]) {
			return mid;
		} else if(key < arr[mid]) {
			high = mid - 1;
		} else {
			low = mid + 1;
		}
	}

	return -1; // 탐색 실패 
}

 

 

이진 탐색의 성능

이진 탐색의 경우 시간 복잡도가 로그 시간인 O(log n)으로 다른 정렬에 비해 상대적으로 매우 빠르다

표기법 이름 시간 복잡도 설명 예시
O(1) 상수 상수 시간 입력 크기와 상관없이 일정한 실행 시간을 가진다. 배열에서 원소 하나 찾기
O(logn) 로그 로그 시간 입력 크기가 증가함에 따라 실행 시간이 로그함수의 형태로 증가한다 이진 탐색 알고리즘
O(n) 선형 선형 시간 입력 크기와 비례하는 실행 시간을 가진다. 선형 탐색 알고리즘
O(nlogn) 로그 선형 선형 로그 시간 입력 크기가 증가함에 따라 실행 시간이 로그함수와 선형 함수의 곱의 형태로 증가한다. 병합 정렬, 힙 정렬 알고리즘
O(n^2) 이차 이차 시간 입력 크기의 제곱에 비례하는 실행 시간을 가진다. 선택 정렬, 버블 정렬, 퀵 정렬 알고리즘
O(2^n) 지수 지수 시간 입력 크기의 지수에 비례하는 실행 시간을 가진다. 부분집합
O(n!) 계승 팩토리얼 시간 입력 크기의 팩토리얼에 비례하는 실행 시간을 가진다. 외판원 문제

 

 

 

 

 

 

References

https://adjh54.tistory.com/187

https://minhamina.tistory.com/127

 

728x90
반응형