이분 탐색이란?
- 정렬된 배열에서 원하는 값의 존재 여부를 찾는 알고리즘.
- 반드시 배열을 정렬해서 사용해야 한다는 단점이 있다.
- 탐색할 때마다 검사 범위가 절반으로 줄어든다.
시간복잡도 : O(log N)
탐색 방식
- 전체 배열의 중간 요소를 찾고자 하는 키로 시작합니다.
- 찾고자 하는 키의 값이 항목과 같으면 찾고자 하는 키의 인덱스를 반환합니다.
- 또는 찾고자 하는키의 값이 Mid보다 작으면 End = Mid - 1으로 좁힙니다.
- 그렇지 않으면 Start = Mid + 1으로 좁힙니다.
- 두 번째 지점부터 값을 찾거나 간격이 비어 있을 때까지 반복적으로 확인합니다.
출처 : https://www.geeksforgeeks.org/binary-search/
Binary Search - GeeksforGeeks
A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
www.geeksforgeeks.org
이분탐색을 이용한 프로그래머스 문제
https://school.programmers.co.kr/learn/courses/30/lessons/43238
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
정답
https://tin9-d-d-blog.tistory.com/111
프로그래머스 입국심사(lv3)
#include #include #include using namespace std; long long solution(int n, vector times) { long long answer = 0; // 호춘쿠키님의 글을 보고 적고 공부내용임 // 주석 걸린내용 대부분 호춘쿠키님의 주석내용(이해가기 쉽게
tin9-d-d-blog.tistory.com
'c++ > 자료구조 간단 이론' 카테고리의 다른 글
| 레드-블랙 트리(Red_Black_Tree) (0) | 2023.05.31 |
|---|---|
| deque 정의 및 시간복잡도 (0) | 2022.08.23 |
| Stack 간단 정의, 시간복잡도 (0) | 2022.08.23 |
| List 간단 정의 성질 및 종류 (0) | 2022.08.23 |
| queue간단 정의, 성질 (0) | 2022.08.23 |
댓글