\uc774\uc9c4 \ud0d0\uc0c9(Binary Search)\uc740 \uc815\ub82c\ub41c \ubc30\uc5f4\uc5d0\uc11c \ud2b9\uc815 \uac12\uc744 \ucc3e\ub294 \ud6a8\uc728\uc801\uc778 \ubc29\ubc95\uc785\ub2c8\ub2e4. \uc774 \uc54c\uace0\ub9ac\uc998\uc740 \ubc30\uc5f4\uc744 \ubc18\ubcf5\uc801\uc73c\ub85c \ubc18\uc73c\ub85c \ub098\ub204\uc5b4 \ubaa9\ud45c \uac12\uc744 \ucc3e\uae30 \ub54c\ubb38\uc5d0 O(log n)\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub97c \uac00\uc9d1\ub2c8\ub2e4. \ubcf8 \uac15\uc758\uc5d0\uc11c\ub294 \uc774\uc9c4 \ud0d0\uc0c9\uc758 \uae30\ubcf8 \uac1c\ub150, \uad6c\ud604 \ubc29\ubc95, \uadf8\ub9ac\uace0 \uc774\ub97c \ud65c\uc6a9\ud55c \uc2e4\uc2b5 \ubb38\uc81c\ub97c \ub2e4\ub8e8\uace0\uc790 \ud569\ub2c8\ub2e4.<\/p>\n
\uc774\uc9c4 \ud0d0\uc0c9\uc740 \ub2e4\uc74c\uacfc \uac19\uc740 \uc808\ucc28\ub85c \ub3d9\uc791\ud569\ub2c8\ub2e4:<\/p>\n
\uc774 \uacfc\uc815\uc744 \ubc18\ubcf5\ud558\uc5ec \ubaa9\ud45c \uac12\uc744 \ucc3e\uc2b5\ub2c8\ub2e4.<\/p>\n
\uc8fc\uc5b4\uc9c4 \uc815\uc218 \ubc30\uc5f4 \ud0c0\uac9f\uc758 \uc778\ub371\uc2a4\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4. (0 \uc774\uc0c1 n-1 \uc774\ud558\uc758 \uc815\uc218)<\/p>\n \uba3c\uc800 \ubb38\uc81c\ub97c \uc815\ud655\ud788 \uc774\ud574\ud558\ub294 \uac83\uc774 \uc911\uc694\ud569\ub2c8\ub2e4. \uc815\ub82c\ub41c \ubc30\uc5f4\uc5d0\uc11c \ud2b9\uc815 \uc694\uc18c\ub97c \ube60\ub974\uac8c \ucc3e\ub294 \uac83\uc774\ub2c8, \uc774\uc9c4 \ud0d0\uc0c9\uc744 \uc774\uc6a9\ud574\uc57c \ud569\ub2c8\ub2e4.<\/p>\n \uc774\uc9c4 \ud0d0\uc0c9 \uc54c\uace0\ub9ac\uc998\uc744 C++\ub85c \uad6c\ud604\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n \n – \ucf54\ub4dc\ub97c \uc791\uc131\ud55c \ud6c4, \ub2e4\uc591\ud55c \ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4\uc5d0 \ub300\ud574 \uc2e4\ud589\ud558\uc5ec \uc62c\ubc14\ub978 \uacb0\uacfc\ub97c \ubc18\ud658\ud558\ub294\uc9c0 \ud655\uc778\ud574\uc57c \ud569\ub2c8\ub2e4. \ub2e4\uc74c\uacfc \uac19\uc740 \ud14c\uc2a4\ud2b8\ub97c \uace0\ub824\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4:<\/p>\n \uc774\uc9c4 \ud0d0\uc0c9\uc740 \ub9e4\uc6b0 \uc720\uc6a9\ud55c \uc54c\uace0\ub9ac\uc998\uc785\ub2c8\ub2e4. \ud2b9\ud788, \uc815\ub82c\ub41c \ubc30\uc5f4\uc5d0\uc11c \uc18d\ub3c4 \uba74\uc5d0\uc11c \ub6f0\uc5b4\ub09c \uc131\ub2a5\uc744 \ubc1c\ud718\ud569\ub2c8\ub2e4. \ubcf8 \uac15\uc758\uc5d0\uc11c\ub294 \uc774\uc9c4 \ud0d0\uc0c9\uc758 \uae30\ubcf8 \uc6d0\ub9ac\ub97c \uc774\ud574\ud558\uace0, \uc2e4\uc81c \ucf54\ub4dc\ub97c \uc791\uc131\ud574\ubcf4\uc558\uc2b5\ub2c8\ub2e4. \uc774\uc9c4 \ud0d0\uc0c9\uc744 \ub9c8\uc2a4\ud130\ud558\uba74, \ub2e4\ub978 \ub9ce\uc740 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ub370\ub3c4 \ud070 \ub3c4\uc6c0\uc774 \ub420 \uac83\uc785\ub2c8\ub2e4.<\/p>\n \ub2e4\uc74c \uac15\uc758\uc5d0\uc11c\ub294 \uc774\uc9c4 \ud0d0\uc0c9\uc758 \ubcc0\ud615 \ubb38\uc81c \ubc0f \ub2e4\uc591\ud55c \uc751\uc6a9 \uc0ac\ub840\uc5d0 \ub300\ud574 \ub2e4\ub8f0 \uc608\uc815\uc785\ub2c8\ub2e4. \uc9c0\uc18d\uc801\uc778 \ud559\uc2b5\uc744 \ud1b5\ud574 \uc54c\uace0\ub9ac\uc998 \ub2a5\ub825\uc744 \ud5a5\uc0c1\uc2dc\ud0a4\uc2dc\uae38 \ubc14\ub78d\ub2c8\ub2e4!<\/p>\narr<\/code>\uc640 \uc815\uc218 target<\/code>\uc774 \uc788\uc744 \ub54c, target<\/code>\uc758 \uc778\ub371\uc2a4\ub97c \ubc18\ud658\ud558\ub294 \ud504\ub85c\uadf8\ub7a8\uc744 \uc791\uc131\ud558\uc2dc\uc624. \ub9cc\uc57d target<\/code>\uc774 \uc5c6\ub294 \uacbd\uc6b0 -1<\/code>\uc744 \ubc18\ud658\ud574\uc57c \ud569\ub2c8\ub2e4.<\/p>\n\uc785\ub825 \ud615\uc2dd<\/h3>\n
\n
n<\/code>\uc774 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4. (1 \u2264 n \u2264 105<\/sup>)<\/li>\narr<\/code>\uac00 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4.<\/li>\ntarget<\/code>\uac00 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4.<\/li>\n<\/ul>\n\ucd9c\ub825 \ud615\uc2dd<\/h3>\n
\uc608\uc81c<\/h4>\n
\uc785\ub825:\n 5\n 1 3 5 7 9\n 5\n\n \ucd9c\ub825:\n 2<\/code><\/pre>\n\ubb38\uc81c \ud480\uc774 \uacfc\uc815<\/h2>\n
1\ub2e8\uacc4: \ubb38\uc81c \uc774\ud574<\/h3>\n
2\ub2e8\uacc4: \uc774\uc9c4 \ud0d0\uc0c9 \uc54c\uace0\ub9ac\uc998 \uad6c\ud604<\/h3>\n
#include <iostream>\n#include <vector>\n\nusing namespace std;\n\nint binarySearch(const vector<int> &arr, int target) {\n int left = 0;\n int right = arr.size() - 1;\n\n while (left <= right) {\n int mid = left + (right - left) \/ 2;\n\n if (arr[mid] == target) {\n return mid; \/\/ \ud0c0\uac9f\uc744 \ucc3e\uc558\ub2e4.\n } else if (arr[mid] < target) {\n left = mid + 1; \/\/ \uc624\ub978\ucabd \ubc18\uc73c\ub85c \uc774\ub3d9.\n } else {\n right = mid - 1; \/\/ \uc67c\ucabd \ubc18\uc73c\ub85c \uc774\ub3d9.\n }\n }\n return -1; \/\/ \ud0c0\uac9f\uc744 \ucc3e\uc9c0 \ubabb\ud588\ub2e4.\n}\n\nint main() {\n int n;\n cout << \"\ubc30\uc5f4\uc758 \ud06c\uae30\ub97c \uc785\ub825\ud558\uc138\uc694: \";\n cin >> n;\n \n vector<int> arr(n);\n cout << \"\ubc30\uc5f4\uc758 \uc694\uc18c\ub97c \uc785\ub825\ud558\uc138\uc694: \";\n for (int i = 0; i < n; i++) {\n cin >> arr[i];\n }\n \n int target;\n cout << \"\ucc3e\uace0\uc790 \ud558\ub294 \uc22b\uc790\ub97c \uc785\ub825\ud558\uc138\uc694: \";\n cin >> target;\n\n int result = binarySearch(arr, target);\n if (result != -1) {\n cout << \"\ud0c0\uac9f\uc758 \uc778\ub371\uc2a4: \" << result << endl;\n } else {\n cout << \"\ud0c0\uac9f\uc744 \ucc3e\uc9c0 \ubabb\ud588\uc2b5\ub2c8\ub2e4.\" << endl;\n }\n\n return 0;\n}<\/code><\/pre>\n3\ub2e8\uacc4: \ucf54\ub4dc \uc124\uba85<\/h3>\n
binarySearch<\/code> \ud568\uc218\ub294 \uc815\uc218 \ubca1\ud130\uc640 \ubaa9\ud45c \uac12\uc744 \uc785\ub825\uc73c\ub85c \ubc1b\uace0, \ubaa9\ud45c \uac12\uc758 \uc778\ub371\uc2a4\ub97c \ubc18\ud658\ud569\ub2c8\ub2e4.
\n – left<\/code>\uc640 right<\/code>\ub294 \ud0d0\uc0c9 \uad6c\uac04\uc758 \uc2dc\uc791\uacfc \ub05d \uc778\ub371\uc2a4\ub97c \ub098\ud0c0\ub0c5\ub2c8\ub2e4.
\n – while<\/code> \ub8e8\ud504\ub294 left<\/code>\uac00 right<\/code>\ubcf4\ub2e4 \uc791\uac70\ub098 \uac19\uc740 \ub3d9\uc548 \uc2e4\ud589\ub429\ub2c8\ub2e4.
\n – \uac01 \ubc18\ubcf5\uc5d0\uc11c \uc911\uc559 \uc778\ub371\uc2a4 mid<\/code>\ub97c \uacc4\uc0b0\ud558\uace0, \uc911\uc559 \uc694\uc18c\uc640 \ubaa9\ud45c \uac12\uc744 \ube44\uad50\ud558\uc5ec \ub2e4\uc74c \ud0d0\uc0c9 \uad6c\uac04\uc744 \uacb0\uc815\ud569\ub2c8\ub2e4.\n <\/p>\n4\ub2e8\uacc4: \ud14c\uc2a4\ud2b8 \ubc0f \uac80\uc99d<\/h3>\n
\n
\uacb0\ub860<\/h2>\n