C++ Lower Bound & Upper Bound

2023. 8. 22. 16:58· BOJ 백준/이분탐색
728x90
반응형

Lower Bound와 Upper Bound는 이진탐색을 기반으로 경계값을 찾는 알고리즘이다.

 

📕Lower Bound

찾고자 하는 값과 같거나 큰 값이 최초로 나타나는 위치. 즉, 특정 값의 시작 위치를 찾는 알고리즘.

 

<로직>

이진탐색 시 mid 값이 target 값보다 작으면 left 값을 mid + 1로,

mid 값이 target 값보다 크다면 right 값을 mid로 한다.

반복이 끝나면 right 값이 lower bound가 된다.

 

int binarySearch(int left, int right, int target) {
  int mid;

  while (left < right) {
    mid = (left + right) / 2;
    if (lis[mid] < target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return right;
}

 

📘Upper Bound

특정 값보다 처음으로 큰 값의 위치를 찾는 알고리즘

 

<로직>

이진탐색 시 mid 값이 target 값보다 작거나 같으면 left 값을 mid+1로,

mid 값이 target 값보다 크다면 right 값을 mid로 한다.

반복이 끝나면 right 값이 lower bound가 된다.

 

int binarySearch(int left, int right, int target) {
  int mid;

  while (left < right) {
    mid = (left + right) / 2;
    if (lis[mid] <= target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return right;
}
728x90
반응형

'BOJ 백준 > 이분탐색' 카테고리의 다른 글

[BOJ] 12015번: 가장 긴 증가하는 부분 수열  (0) 2023.08.22
[BOJ] 2565번: 전깃줄  (0) 2023.08.22
[BOJ] 1920번: 수 찾기  (0) 2022.04.19
[BOJ] 2805번: 나무 자르기  (0) 2021.07.29
'BOJ 백준/이분탐색' 카테고리의 다른 글
  • [BOJ] 12015번: 가장 긴 증가하는 부분 수열
  • [BOJ] 2565번: 전깃줄
  • [BOJ] 1920번: 수 찾기
  • [BOJ] 2805번: 나무 자르기
코블리_vv
코블리_vv
코블리_vv
코딩 놀이터
코블리_vv
전체
오늘
어제
  • 분류 전체보기 (67)
    • CS 노트 (1)
    • 대외활동 (0)
      • 창업 동아리 (0)
    • AWS (0)
      • AWS Academy Cloud Architect.. (0)
      • AWS Lab (0)
    • 웹 개발 노트 (3)
      • 웹 프로젝트 (0)
      • 스프링 인 액션 (0)
      • 스프링 입문을 위한 자바 객체 지향의 원리와 이해 (0)
    • ORACLE (0)
    • TOPCIT (2)
      • M1 소프트웨어 개발 (2)
      • M2 데이터 이해와 활용 (0)
    • 캡스톤 (5)
    • BOJ 백준 (53)
      • 브루트포스 (1)
      • 정렬 (6)
      • 이분탐색 (5)
      • 맵 (2)
      • 다이나믹 프로그래밍 (11)
      • 수학 (5)
      • 그리디 (3)
      • 분할정복 (4)
      • DFS (3)
      • BFS (6)
      • 그래프 (4)
      • 자료구조 (1)
      • 백트래킹 (2)
    • 코딩 테스트 (0)
      • 코드트리 (0)
    • 대회 (0)
    • Spring Boot (3)
      • JPA (3)

블로그 메뉴

  • 홈
  • 태그
  • 알고리즘
  • BOJ 백준
  • 방명록

공지사항

인기 글

태그

  • 투자 전략
  • 분할정복
  • 파이썬 backtrader
  • 다이나믹프로그래밍
  • computer security
  • dfs
  • 시스템 트레이딩
  • 다이나믹 프로그래밍
  • java
  • 암호학
  • dp
  • 백트래킹
  • 우선순위 큐
  • spring
  • backtrader
  • 이분탐색
  • 웹개발
  • 백준 n과m
  • 백준 토마토
  • 1676
  • binary search
  • 재귀
  • 그리디 알고리즘
  • BFS
  • 컴퓨터 보안
  • 투자
  • 플로이드 와샬
  • 스프링인액션
  • n과m
  • 너비우선탐색

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
코블리_vv
C++ Lower Bound & Upper Bound
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.