Algorithm Binary search and find boundary

알고리듬 Binary search and find boundary를 알아보겠습니다.

​
Binary search는 이진 탐색으로 찾는 시간이 O(log n)으로 빠릅니다.



이론은 다음과 같습니다.

2, 3, 5, 7, 11이라는 배열이 있습니다.








여기서 7을 찾아봅시다.

​

가장 왼쪽을 left, 가장 오른쪽을 right로 두고, 그 가운데를 middle로 둡니다.







찾으려는 숫자(7)가 가운데(5)를 기준으로 오른쪽에 있으므로 왼쪽은 모두 제외합니다.

middle이 있던 자리에 left로 만들고 또 가운데를 찾습니다.

middle(7)과 찾으려는 숫자(7)이 같으므로 찾았습니다.







코드로 봅시다.







위의 방법 말고도 다른 방법이 있습니다.

위의 코드는 middle이 target과 같은지 항상 체크를 합니다. 아래의 코드는 항상 확인하지 않고 한 번 만 확인합니다.







찾으려는 값이 가장 왼쪽(leftmost)에 있는 값을 찾으려면 아래와 같이 사용합니다.









찾으려는 값이 가장 오른쪽(rightmost)에 있는 값을 찾으려면 아래와 같이 합니다.







끝.



카테고리: Algorithm

댓글

이 블로그의 인기 게시물

음악 총보(Score), 파트보(Part)

딩기 요트 명칭

일본어 문장부호

KiCad 시작하기 3 (새로운 소자 추가하기)

Android Custom IME(Input method editor) 만들기

Python urllib.parse.quote()

Python OpenCV 빈 화면 만들기

KiCad 시작하기 2 (PCB 만들기)

Android GDPR Consent 사용

KiCad 시작하기 1 (회로도 만들기)