이분탐색

탐색 범위를 절반씩 줄여가며 탐색하는 방법

<aside> 🔥 꼭 배열 내부 데이터가 정렬되어 있어야 함

</aside>

순차적으로 하나씩 찾기 보다는 시간이 훨씬 절약된다!

1920번: 수 찾기

구현 방법

기본 틀은 위의 영상과 같이 low와 high를 옮겨가며 mid 값으로 비교한다

(start, end로 표현하겠다)

배열의 크기가 n이고 안에 정렬된 수가 있다고 가정한다면…

찾아야 하는 수를 뒤져봐야 할 범위는 ..→ 0부터 n-1까지가 됨!

→ start = 0, end = n-1이 된다

이후 반복하면서

1. mid = (start + end)/2 start ……… mid …………end 와 같이 배열이 가리켜진다
2. arr[mid]와 tmp 와 비교 !!!
3. 만약 arr[mid] 가 찾는 수와 같다면 찾기 성공!
4. 찾고자 하는 수가 arr[mid]보다 더 크다면…? → 찾고자 하는 수는 mid+1과 end 사이에 있다!! 따라서 start = mid+1로 해서 찾는 범위를 mid+1 ~ end로 바꿔줌