이진(이분) 탐색 (Binary Search)

bool binarySearch(vector<int> &list, int findNum) {
	int start = 0;
	int end = list.size() - 1;
	

	while (start <= end) {
		int mid = (end + start) / 2;
		if (findNum == list[mid]) return true;
		else if (findNum < list[mid]) end = mid - 1;
		else start = mid + 1;
	}
	return false;
}

이분 탐색
정렬 되어 있는 배열에서 데이터를 찾을 때 모든 원소를 순회하여 찾는 것이 아니라 탐색 범위를 절반씩 줄여가는 탐색 방법
1 2 3 4 5 6 이라는 값에서 6을 찾는다고 하면 배열의 중간 값인 3과 6을 비교한다. 6이 3보다 크기 때문에 3보다 왼쪽에 위치하는 값들은 탐색할 필요가 없으므로 3보다 오른 쪽에 있는 값들로만 탐색한다. 그렇게 되면 남은 원소는 4 5 6 이므로 중간 값이 된 5와 찾는 값인 6을 비교하여 6은 5보다 크므로 5의 오른쪽 값들로만 다시 탐색한다. 그러면 6만 남게 되는데, 찾는 값 또한 6이므로 탐색을 종료한다.


순차 탐색의 시간 복잡도는 O(n)이지만 이분 탐색을 사용하면 시간 복잡도를 O(logN)으로 줄일 수 있다.