이진탐색(Binary Search)
- 이진탐색의 조건
- 정렬된 데이터가 저장된 배열
- 시간복잡도의 평균적 케이스(average case)
#include <stdio.h> #include <iostream> int L_Search(int arr[], int length, int target) // 순차 알고리즘 { int first = 0; // 시작 인덱스 int last = length - 1; // 마지막 인덱스 int middle; // 중앙 인덱스 while (first <= last) { middle = (first + last) / 2; // 중앙값 찾기 if (target == arr[middle]) // 중앙값이 타겟과 같다는 조건 { printf("검색 완료 값 : %d \n", middle); return middle; // 검색된 값 리턴 } else { if (target < arr[middle]) { last = middle - 1; } else { first = middle + 1; } } } printf("검색 실패 \n"); return -1; } void main() { int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 10 }; L_Search(arr, sizeof(arr) / sizeof(int), 3); L_Search(arr, sizeof(arr) / sizeof(int), 9); system("pause"); } |
결과값)
'알고리즘&자료구조' 카테고리의 다른 글
| 알고리즘(algorithm) 순차 탐색(Linear Search) (0) | 2017.12.11 |
|---|---|
| 알고리즘(algorithm) 이란? (0) | 2017.12.08 |
| 자료구조(Data structure) 란? (0) | 2017.12.08 |