1. 이진 탐색을 하기 위해서 필요한 것, 인덱스, 키, 그리고 찾았다 안찾았다. 이런 변수가 필요합니다. 정렬이 되어 있어야 합니다. 헤드와 미드가 있고, 미드의 인덱스 데이터가 그 안에 있으면 그 안에 없으면 각각 미드를 수정합니다. 그리고 데이터가 미드와 같으면 키를 출력하면 됩니다. 오께이. 그리고 찾으면 break 를 하도록 합니다. 이전에 배열에서 이동하기 문제를 풀어보도록 하겠습니다. 이것을 응용 하면 되겠습니다. |
#include <iostream> using namespace std; void main() { int data[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14 }; int n = 14; int index = -1; int key; cin >> key; int head = 0; int tail = n; int mid = (head + tail) / 2; while (head <= tail) { if (data[mid] < key) { head = mid + 1; mid = (head + tail) / 2; } else if (data[mid] > key) { tail = mid - 1; mid = (head + tail) / 2; } else if (data[mid] == key) { index = mid; break; } } if (index == -1) { cout << "can't find" << endl; } else { cout << "KEY : " << key << endl; cout << "INDEX : " << index << endl; } } |