이진 탐색

이진 탐색(Binary Search)은 정렬된 리스트에서 특정한 값을 찾는 알고리즘임.

이진 탐색은 리스트의 중간 값을 기준으로 탐색 범위를 반씩 줄여가며 값을 찾아나감

 

이진 탐색의 동작 방식!

리스트의 중간 위치를 찾습니다.

중간 위치의 값과 찾고자 하는 값이 일치하면 탐색을 종료합니다.

중간 위치의 값이 찾고자 하는 값보다 크면, 중간 위치의 왼쪽 부분 리스트에서 탐색을 계속합니다.

중간 위치의 값이 찾고자 하는 값보다 작으면, 중간 위치의 오른쪽 부분 리스트에서 탐색을 계속합니다.

리스트에서 찾고자 하는 값이 없으면 탐색을 종료합니다.

 

이진 탐색은 탐색 범위가 매우 큰 리스트에서도 빠른 속도로 값을 찾을 수 있음

탐색 범위를 반씩 줄여가며 탐색하기 때문에 최대 log2(N)번의 비교 연산이 필요함. 여기서 N은 리스트의 크기임. 이진 탐색의 시간 복잡도는 O(log N)

 

이진 탐색은 리스트가 정렬된 상태에서만 사용할 수 있음.

 따라서 리스트의 값이 변경되는 경우 이진 탐색을 다시 수행해야 합니다.

 

 

• 정렬된 배열을 이용해서 이진탐색 가능(numbers[mid])
• 배열의 단점(중간에 삽입,삭제 가 느리다) 그렇기 때문에 배열이 변하지 않는 다는 가정하에 효율적
• 정렬된 연결 리스트로는 불가 (임의접근 X)

코드로 작성해보자

 

#include <iostream>
#include <vector>
#include <stack>
#include <list>
#include <queue>
using namespace std;

//이진 탐색 트리

//상황) 배열에 데이터가 정렬되어 있다.

vector<int> numbers;

void BinarySearch(int N)
{
	int left = 0;
	int right = (int)numbers.size() - 1;

	while (left <= right)
	{
		cout << "탐색범위 : " << left << "-" << right << endl;
		int mid = (left + right) / 2;

		if (N < numbers[mid])
		{
			cout << N << "<" << numbers[mid] << endl;
			right = mid - 1;
		}
		else if (N > numbers[mid])
		{
			cout << N << ">" << numbers[mid] << endl;
			left = mid + 1;
		}
		else
		{
			cout << "찾음!" << endl;
			break;
		}
	}
}

int main()
{
	numbers = vector<int>{ 1, 8, 15, 23, 32, 44, 56, 63, 81, 91 };
	BinarySearch(81);

	return 0;
}

여기서 81 대신 다른값을 넣으면 찾지 못함