[탐색] 이진탐색 (Binary Search )

int BSearch(vector<int>& v, int k) {
	int low = 0;
	int high = v.size() - 1;
	int mid;

	while (low <= high) {
		mid = (low + high) / 2;
		if (v[mid] == k)
			return mid;
		else if (v[mid] > k)
			high = mid - 1;
		else low = mid + 1;
	}
	return -1;
}

시간 복잡도

평균 시간복잡도 = O(logn)

최악 시간복잡도 = O(logn)

 

알고리즘

1.  mid 값설정

2. v[mid] 값이 k 와 같다면 리턴

3. v[mid] > k 이면 high = mid + 1 로 설정 (이미 정렬되어있기 때문에 mid + 1 초과로는 탐색할 필요 없음)

4. v[mid] < k 이면 low = mid + 1

5. 반복