이진 검색 (binary search) : 정렬이 되어 있어야 한다.
어떠한 수가 배열 내에 있는지를 빠르게 찾고 싶습니다. 그럴 때, 이진 검색, binary search를 이용할 수 있습니다. 그런데, 전제 조건은 정렬이 되어 있어야 한다는 것입니다. 왜 그럴까요? 정렬이 되어 있지 않다고 해 봅시다. 중앙에 있는 3을 기준으로 9는 왼쪽에 있고 오른쪽에 없을 수도 있어요. 그러면 3을 기준으로 왼쪽에서 찾아야 합니다. 그런데, 이런 경우도 있을 수가 있어요. 중앙에 있는 3을 기준으로 좌측에 없고, 우측에 있다. 이런 경우는 또 어떤가요? 내가 있는 위치를 기준으로 9가 왼쪽에 있을 수도 있고, 오른쪽에 있을 수도 있고, 없을 수도 있기 때문에, 현재 탐색하는 위치를 기준으로 절반씩 해를 좁혀나갈 수가 없어요. 따라서, 선형 탐색으로 해결을 할 수 밖에 없을 거에요...
자료알고/알고리즘
2019. 7. 19. 00:10
최근댓글