재원블로그 재원블로그

이진 탐색은 정렬되어 있는 요소들에게만 사용할 수 있다. 일반적인 순차 탐색으로는 O(N)의 시간이 소요되지만, 이진 탐색을 사용하면 O(log N) 시간이 소요된다. C++로 구현한 기본적인 구현은 다음과 같다. int binarySearch(int key) { int low = 0; int high = MAX - 1; while (low arr[mid]) { low = mid + 1; } else if (key < arr[mid]) { high = mid - 1; } else { return mid; } } return -1; } 이 코드는 key가 정해진 배열에 존재하는지 여부를 판단할 수 있고, 만약 있다면 그 인덱스를 리턴하고, 없다면 -1을 리턴한다. 배열에서 key의 존재 유무를 판단하는 것..