[자료구조] 이진탐색

🎞️ 이진탐색

이진 탐색: 데이터가 정렬된 배열에서 특정값을 찾아내는 알고리즘

• 배열의 중간에 있는 임의의 값을 선택해 찾고자하는 값과 비교
• 찾고자 하는 값보다 중간 값이 작으면 중간 값을 기준으로 좌측의 데이터 대상으로 다시 탐색
• 찾고자 하는 값보다 중간 값이 크면 중간 값을 기준으로 우측의 데이터 대상으로 다시 탐색
• 해당 값을 찾을 때까지 이 과정 반복

시간복잡도: O(log N)

🎞️ Lower Bound

내가 목표하는 값이 들어갈 수 있는 가장 왼쪽 범위 index

if (mid < target) {
	left = mid + 1
} else {
	right = mid
}

목표 결과 값은 left

🎞️ Upper Bound

Target보다 큰 첫번째 위치를 찾는 것

if (mid <= target) {
	left = mid + 1
} else {
	right = mid
}

목표 결과 값은 left

---

참고:

• 이진 탐색(Binary Search) 알고리즘 개념 이해 및 추가 예제
• Binary Search Lower Bound와 Upper Bound