[이코테/C++] 5. 이진 탐색

목차

출처
개념
특징
로직
예제문제

 

---

출처

(이코테 2021 강의 몰아보기) 5. 이진 탐색

 

(이코테 2021 강의 몰아보기) 5. 이진 탐색

---

 

개념

• 탐색 범위를 절반씩 좁히며 데이터 탐색
• 범위 설정 : 시작점, 끝점, 중간점(소수점 이하 제거) 이용
• 조건 : 정렬 완료된 상태 

시간 복잡도

$ O\left ( log(N) \right ) $

 

---

구현

#include <iostream>
#include <vector>

using namespace std;

// 오름차순된 리스트
vector<int> v = { 1, 2, 3, 4, 5 };

// target 찾기
int binarySearch(int target, int start, int end) {
	while (start <= end) {
		// 중간값 : 소수점 버리기
		int mid = (start + end) / 2;

		// 찾으면 인덱스 반환
		if (v[mid] == target) return mid;
		// target이 중간값보다 작으면, 중간값보다 왼쪽(더 작은 쪽)을 탐색
		else if (v[mid] > target) end = mid - 1;
		// target이 중간값보다 크면, 중간값보다 오른쪽(더 큰 쪽)을 탐색
		else start = mid + 1;
	}

	return -1; // 못 찾을 때
}

int main() {
	int target = 3;
	int start = 0, end = v.size() - 1;
	int result = binarySearch(target, start, end);

	if (result == -1) cout << "존재하지 않음";
	else cout << "v[" << result << "] = " << target;
	return 0;
}

---

예제 문제

[백준]

이분탐색

1920 수 찾기