2022/11/14 - 이분 탐색

풀이 흐름

1. 초기 설정

가장 낮은 위치(lowest)와 가장 높은 위치(highest)가 있을 때(배열의 index를 많이 사용한다) 그 위치의 중간 위치(mid, Math.floor((lowest + highest)/2)를 구한다

1. 중간점 이동

[1] 목표의 위치보다 중간점이 크다면, 가장 낮은 위치를 중간점으로 바꾼다.

lowest = mid

[2] 목표의 위치보다 중간점이 작다면, 가장 높은 위치를 중간점으로 바꾼다

highest = mid

[3] 목표의 위치와 중간점이 같다면 return 합니다.

1~2를 반복한다

 

흐름과 조건 기억하기

이분 탐색 문제를 풀면서 가장 기억 안났던 것은 1~2를 반복하는 조건이다. 이분 탐색에서의 반복(정지)조건은 가장 낮은 점과 가장 높은점이 교차할 때이다.