-
Binary Serach알고리즘 2020. 3. 16. 20:57
Binary Search 이진탐색
- 순차 탐색 : 처음부터 끝까지 하나씩 모든 데이터를 체크하여 값을 찾는 방법.
- 이진 탐색 : 탐색 범위를 절반씩 줄어가며 값을 찾는 방법. 탐색 전, 배열이 미리 정렬되어 있어야한다.
배열의 크기가 N이라고 할때,순차탐색
이진탐색
시간복잡도
O(N)
O(log N)
- 탐색 방법
크기가 N인 배열 arr에서, target을 찾는다고 가정 시- start = 0, end = N-1 로 초기화 한다.
- mid = (start + end) / 2 로 초기화 한다.
- target과 arr[mid]의 값을 비교한다. 값이 같을 시, 탐색을 종료
같지 않을시, target < data[mid] 이면 end = mid-1로 업데이트 후 2번으로 돌아감target > data[mid] 이면 start = mid+1로 업데이트 후 2번으로 돌아감- 문제에서 사용할 때의 while문?
while(end > start)면 start = mid + 1, end = midwhile(end >= start)면 start = mid + 1, end = mid - 1'알고리즘' 카테고리의 다른 글
Greedy Algorithm (0) 2020.03.17 Floyd-Warshall (0) 2020.03.17 Dijkstra (0) 2020.03.17 DP (0) 2020.03.16 DFS & BFS (0) 2020.03.16