수 찾기1 [이진탐색] 1920 수 찾기, Binary search Binary search는 '정렬된 배열'에서 특정 원소를 찾을 때, O(logN)의 탐색시간을 보장합니다. 따라서, O(N)만큼 걸리는 Linear search 보다는 성능이 좋을 수 있습니다. 처음에는 재귀함수로 구현하였고, 이와 거의 비슷하게 반복문으로 구현할 수 있었습니다. #include #include int a[100001]; // array는 정렬되어 있어야 함. int binarySearch(int first, int last, int k){ int mid = (first + last) / 2; if (first > last) return -1; else { if (a[mid] == k) return mid; else { if (a[mid] < k){ binarySearch(mid + 1.. 2019. 8. 29. 728x90 이전 1 다음
