Algorithm Binary search and find boundary

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

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

https://en.wikipedia.org/wiki/Binary_search_algorithm

이론은 다음과 같습니다.

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

여기서 7을 찾아봅시다.

​

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

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

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

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

코드로 봅시다.

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

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

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

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

끝.

카테고리: Algorithm