-
이분 탐색(binary search)알고리즘 2024. 2. 25. 21:48
int search(int *arr, int n, int size) { int start = 0, end = size - 1; int now; while (start <= end) { now = (start + end) / 2; if (arr[now] == n) { return 1; } else if(arr[now] > n){ end = now - 1; } else { start = now + 1; } } return 0; }
게임 만들다 까먹은 게 많아서 코딩 연습 문제를 풀고 있습니다.
그런데 이분 탐색 while문 내부 구현을 까먹어서 나중에 헷갈리지 안도록 기록용으로 남겨둡니다.
시작, 중간, 끝
조건: 시작 지점이 끝 지점 "이하"
c++의 sort 시간 복잡도는 O(nlog(n)), 이분탐색의 시간복잡도는 O(log(n))
정렬이 안된 배열이라 하면 (n+1)log(n)이니 그냥 O(nlog(n))이라 보면 됩니다.
'알고리즘' 카테고리의 다른 글
스택 응용, 백준 9935: 문자열 폭발 (0) 2024.03.05 에라토스테네스의 체 (0) 2024.03.04 이분탐색 3 - LIS (Longest Increasing Subsequence), 백준 12105 (0) 2024.03.02 이진탐색 2 - Parametric Search, 백준 1654 (0) 2024.03.02