{"id":23537,"date":"2023-01-28T15:26:05","date_gmt":"2023-01-28T08:26:05","guid":{"rendered":"https:\/\/kiencang.net\/?p=23537"},"modified":"2023-08-26T17:59:27","modified_gmt":"2023-08-26T10:59:27","slug":"tim-kiem-nhi-phan","status":"publish","type":"post","link":"https:\/\/kiencang.net\/tim-kiem-nhi-phan\/","title":{"rendered":"T\u00ecm ki\u1ebfm nh\u1ecb ph\u00e2n [serial v\u1ec1 c\u00e1c thu\u1eadt to\u00e1n c\u01a1 b\u1ea3n trong l\u1eadp tr\u00ecnh]"},"content":{"rendered":"\n
T\u00ecm ki\u1ebfm nh\u1ecb ph\u00e2n (binary search) l\u00e0 m\u1ed9t trong c\u00e1c thu\u1eadt to\u00e1n c\u01a1 b\u1ea3n trong l\u1eadp tr\u00ecnh m\u00e0 ch\u00fang ta c\u0169ng c\u1ea7n ph\u1ea3i bi\u1ebft. \u01afu \u0111i\u1ec3m c\u1ee7a n\u00f3 l\u00e0 t\u1ed1c \u0111\u1ed9 t\u1ed1t (v\u00ed d\u1ee5 khi so v\u1edbi t\u00ecm ki\u1ebfm tuy\u1ebfn t\u00ednh \/ tu\u1ea7n t\u1ef1<\/a>) tr\u00ean c\u00e1c m\u1ea3ng c\u00f3 s\u1ed1 l\u01b0\u1ee3ng ph\u1ea7n t\u1eed l\u1edbn, ngo\u00e0i ra, t\u00ecm ki\u1ebfm nh\u1ecb ph\u00e2n c\u0169ng d\u1ec5 hi\u1ec3u n\u1eefa.<\/p>\n\n\n\n M\u1ed9t y\u00eau c\u1ea7u trong t\u00ecm ki\u1ebfm nh\u1ecb ph\u00e2n l\u00e0 m\u1ea3ng m\u00e0 n\u00f3 c\u1ea7n t\u00ecm ki\u1ebfm c\u1ea7n ph\u1ea3i \u0111\u01b0\u1ee3c s\u1eafp x\u1ebfp<\/a> r\u1ed3i (ch\u1eb3ng h\u1ea1n b\u1eb1ng quick sort<\/a>). <\/p>\n\n\n\n V\u00ed d\u1ee5, h\u00e3y t\u00ecm v\u1ecb tr\u00ed c\u1ee7a gi\u00e1 tr\u1ecb 75 trong m\u1ea3ng sau: <\/p>\n\n\n\n N\u1ebfu trong t\u00ecm ki\u1ebfm tuy\u1ebfn t\u00ednh, n\u00f3 s\u1ebd duy\u1ec7t qua t\u1ea5t c\u1ea3 ph\u1ea7n t\u1eed c\u1ee7a m\u1ea3ng, r\u1ed3i so kh\u1edbp xem ph\u1ea7n t\u1eed \u0111\u00f3 c\u00f3 \u0111\u00fang l\u00e0 ph\u1ea7n t\u1eed c\u1ea7n t\u00ecm ki\u1ebfm kh\u00f4ng, sau \u0111\u00f3 tr\u1ea3 v\u1ec1 k\u1ebft qu\u1ea3 v\u1ecb tr\u00ed. <\/p>\n\n\n\n T\u00ecm ki\u1ebfm nh\u1ecb ph\u00e2n ho\u1ea1t \u0111\u1ed9ng th\u00f4ng minh h\u01a1n, v\u00ec m\u1ea3ng \u0111\u00e3 \u0111\u01b0\u1ee3c s\u1eafp x\u1ebfp, n\u00ean n\u00f3 chia \u0111\u00f4i m\u1ea3ng ra th\u00e0nh 2 m\u1ea3ng nh\u1ecf l\u00e0 A v\u00e0 B, r\u1ed3i \u0111em so s\u00e1nh ph\u1ea7n t\u1eed c\u1ea7n t\u00ecm ki\u1ebfm v\u1edbi ph\u1ea7n t\u1eed cu\u1ed1i c\u1ee7a m\u1ea3ng A, n\u1ebfu n\u00f3 \u0111\u00fang b\u1eb1ng ph\u1ea7n t\u1eed n\u00e0y th\u00ec \u0111\u00e2y l\u00e0 ph\u1ea7n t\u1eed c\u1ea7n t\u00ecm, n\u1ebfu n\u00f3 nh\u1ecf h\u01a1n th\u00ec ph\u1ea7n t\u1eed c\u1ea7n t\u00ecm s\u1ebd n\u1eb1m trong m\u1ea3ng A, n\u1ebfu n\u00f3 l\u1edbn h\u01a1n th\u00ec ph\u1ea7n t\u1eed c\u1ea7n t\u00ecm s\u1ebd n\u1eb1m trong m\u1ea3ng B. <\/p>\n\n\n\n Nh\u01b0 v\u1eady, th\u00f4ng qua m\u1ed9t thao t\u00e1c so s\u00e1nh, n\u00f3 \u0111\u1ee1 \u0111\u01b0\u1ee3c 1\/2 c\u00f4ng s\u1ee9c duy\u1ec7t c\u1ea3 m\u1ea3ng, kh\u00f4ng gian t\u00ecm ki\u1ebfm c\u1ee7a n\u00f3 thu h\u1eb9p r\u1ea5t nhanh, gi\u00fap qu\u00e1 tr\u00ecnh n\u00e0y c\u00f3 t\u1ed1c \u0111\u1ed9 t\u1ed1t. Qu\u00e1 tr\u00ecnh ph\u00e2n \u0111\u00f4i (nh\u1ecb ph\u00e2n) n\u00e0y c\u1ee9 ti\u1ebfp t\u1ee5c cho \u0111\u1ebfn khi n\u00f3 t\u00ecm \u0111\u01b0\u1ee3c v\u1ecb tr\u00ed ch\u00ednh x\u00e1c.<\/p>\n\n\n\n \u0110o\u1ea1n m\u00e3 PHP \u0111\u1ec3 l\u00e0m vi\u1ec7c n\u00e0y:<\/p>\n\n\n\n Qu\u00e1 tr\u00ecnh n\u00e0y di\u1ec5n ti\u1ebfn nh\u01b0 sau:<\/p>\n\n\n\n L\u1ea7n 1:<\/p>\n\n\n\n L\u1ea7n 2:<\/p>\n\n\n\n L\u1ea7n 3: <\/p>\n\n\n\n L\u1ea7n 4:<\/p>\n\n\n\n M\u1ed9t s\u1ed1 l\u01b0u \u00fd:<\/p>\n\n\n\n T\u00ecm ki\u1ebfm nh\u1ecb ph\u00e2n (binary search) l\u00e0 m\u1ed9t trong c\u00e1c thu\u1eadt to\u00e1n c\u01a1 b\u1ea3n trong l\u1eadp tr\u00ecnh m\u00e0 ch\u00fang ta c\u0169ng c\u1ea7n ph\u1ea3i bi\u1ebft. \u01afu \u0111i\u1ec3m c\u1ee7a n\u00f3 l\u00e0 t\u1ed1c \u0111\u1ed9 t\u1ed1t (v\u00ed d\u1ee5 khi so v\u1edbi t\u00ecm ki\u1ebfm tuy\u1ebfn t\u00ednh \/ tu\u1ea7n t\u1ef1) tr\u00ean c\u00e1c m\u1ea3ng c\u00f3 s\u1ed1 l\u01b0\u1ee3ng ph\u1ea7n t\u1eed l\u1edbn, ngo\u00e0i ra, …<\/p>\n","protected":false},"author":1,"featured_media":24638,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[333],"tags":[335],"yoast_head":"\n1, 3, 4, 7, 9, 32, 45, 57, 68, 75, 92, 101<\/code><\/pre>\n\n\n\n
function binary_search($arr, $x)\n{\n $left = 0;\n $right = count($arr) - 1;\n while ($left <= $right) {\n $mid = intval(($left + $right) \/ 2); \/\/ l\u1ea5y ph\u1ea7n nguy\u00ean\n if($arr[$mid] == $x) { \/\/ n\u1ebfu \u0111\u00fang b\u1eb1ng gi\u00e1 tr\u1ecb c\u1ea7n t\u00ecm\n return $mid; \/\/ ra \u0111\u01b0\u1ee3c v\u1ecb tr\u00ed\n $left = $right + 1; \/\/ k\u1ebft th\u00fac\n }\n else if ($x < $arr[$mid]) {\n\/\/ b\u1ecf \u0111i ph\u1ea7n t\u1eed $arr[$mid], kh\u00f4ng ph\u1ea3i so n\u1eefa, v\u00e0 thu h\u1eb9p v\u00f9ng t\u00ecm ki\u1ebfm\n $right = $mid - 1; \n }\n else {\n\/\/ b\u1ecf \u0111i ph\u1ea7n t\u1eed $arr[$mid], kh\u00f4ng ph\u1ea3i so n\u1eefa, v\u00e0 thu h\u1eb9p v\u00f9ng t\u00ecm ki\u1ebfm\n $left = $mid + 1;\n }\n }\n\/\/ khi n\u00f3 kh\u00f4ng t\u00ecm th\u1ea5y\n return -1;\n}\n\n$arr = array(1, 3, 4, 7, 9, 32, 45, 57, 68, 75, 92, 101);\necho binary_search($arr, 75); \/\/ k\u1ebft qu\u1ea3 l\u00e0 9, l\u00e0 v\u1ecb tr\u00ed c\u1ee7a ph\u1ea7n t\u1eed 75 trong m\u1ea3ng<\/code><\/pre>\n\n\n\n
\n
\n
\n
\n
\n\n\n\n\n