Thuật toán tìm kiếm nhị phân ( nâng cao 2 )

Home Lớp 7 Tin học lớp 7 - Sách kết nối tri thức Bài 15: Thuật toán tìm kiếm nhị phânBài tập nâng cao

{"common":{"save":0,"post_id":"9793","level":3,"total":10,"point":10,"point_extra":0},"segment":[{"id":"11769","post_id":"9793","mon_id":"1160119","chapter_id":"1160137","question":"Cho dãy s\u1ed1 \u0111ã s\u1eafp x\u1ebfp: D = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Khi áp d\u1ee5ng thu\u1eadt toán tìm ki\u1ebfm nh\u1ecb phân \u0111\u1ec3 tìm s\u1ed1 23, \u1edf b\u01b0\u1edbc so sánh \u0111\u1ea7u tiên, giá tr\u1ecb c\u1ee7a ph\u1ea7n t\u1eed \u1edf gi\u1eefa (ph\u1ea7n t\u1eed mid) là bao nhiêu?<\/p>","options":["A. 12","B. 16","C. 23","D. 38"],"correct":"2","level":"3","hint":"","answer":"\u0110áp án \u0111úng: B. 16<\/strong><\/span> Dãy s\u1ed1 ban \u0111\u1ea7u [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] B\u01b0\u1edbc 1: left = 0, right = 9 → mid = (0 + 9)\/\/2 = 4 → D[4] = 16 So sánh D[4] = 16 v\u1edbi 23 → 23 > 16 → Tìm bên ph\u1ea3i B\u01b0\u1edbc 2: left = 5, right = 9 → mid = (5 + 9)\/\/2 = 7 → D[7] = 56 So sánh D[7] = 56 v\u1edbi 23 → 23 < 56 → Tìm bên trái B\u01b0\u1edbc 3: left = 5, right = 6 → mid = (5 + 6)\/\/2 = 5 → D[5] = 23. Tìm th\u1ea5y! Nh\u01b0ng câu h\u1ecfi ch\u1ec9 h\u1ecfi \u1edf b\u01b0\u1edbc \u0111\u1ea7u tiên, nên: Giá tr\u1ecb ph\u1ea7n t\u1eed \u1edf gi\u1eefa \u1edf b\u01b0\u1edbc \u0111\u1ea7u là D[4] = 16<\/p>","type":"choose","extra_type":"classic","time":"0","user_id":"151","test":"0","date":"2025-07-30 15:42:02","option_type":"txt","len":0},{"id":"11770","post_id":"9793","mon_id":"1160119","chapter_id":"1160137","question":"M\u1ed9t danh sách \u0111i\u1ec3m s\u1ed1 \u0111\u01b0\u1ee3c s\u1eafp x\u1ebfp theo th\u1ee9 t\u1ef1 t\u0103ng d\u1ea7n nh\u01b0 sau: [1, 3, 5, 7, 9, 11, 13, 15, 17] S\u1eed d\u1ee5ng thu\u1eadt toán tìm ki\u1ebfm nh\u1ecb phân \u0111\u1ec3 tìm s\u1ed1 13, hãy cho bi\u1ebft bao nhiêu l\u1ea7n so sánh là c\u1ea7n thi\u1ebft \u0111\u1ec3 tìm ra giá tr\u1ecb này?<\/p>","options":["A. 1","B. 2","C. 3","D. 4"],"correct":"2","level":"3","hint":"","answer":"\u0110áp án \u0111úng: B. 2<\/strong><\/span> Dãy s\u1ed1 ban \u0111\u1ea7u: [1, 3, 5, 7, 9, 11, 13, 15, 17] Danh sách có 9 ph\u1ea7n t\u1eed (ch\u1ec9 s\u1ed1 t\u1eeb 0 \u0111\u1ebfn 8): L\u1ea7n 1: Gi\u1eefa là (0 + 8) \/\/ 2 = 4 → ph\u1ea7n t\u1eed 9 → 13 > 9 → tìm bên ph\u1ea3i (t\u1eeb ch\u1ec9 s\u1ed1 5 \u0111\u1ebfn 8) L\u1ea7n 2: Gi\u1eefa là (5 + 8) \/\/ 2 = 6 → ph\u1ea7n t\u1eed 13 → 13 = 13 → Tìm th\u1ea5y k\u1ebft qu\u1ea3 T\u1ed5ng c\u1ed9ng có 2 l\u1ea7n so sánh, nh\u01b0ng n\u1ebfu theo logic c\u1ea9n th\u1eadn, h\u1ecdc sinh có th\u1ec3 b\u1ecb lúng túng, vì sau l\u1ea7n 2 \u0111ã tìm \u0111\u01b0\u1ee3c → V\u1eady ta \u0111i\u1ec1u ch\u1ec9nh l\u1ea1i \u0111áp án \u0111úng là B. 2<\/p>","type":"choose","extra_type":"classic","time":"0","user_id":"151","test":"0","date":"2025-07-30 15:42:34","option_type":"txt","len":0},{"id":"11771","post_id":"9793","mon_id":"1160119","chapter_id":"1160137","question":"Cho dãy s\u1ed1 A = [11, 22, 33, 44, 55, 66, 77]. \u0110\u1ec3 tìm s\u1ed1 77 b\u1eb1ng thu\u1eadt toán tìm ki\u1ebfm nh\u1ecb phân, c\u1ea7n th\u1ef1c hi\u1ec7n bao nhiêu l\u1ea7n so sánh?<\/p>","options":["A. 1 l\u1ea7n","B. 2 l\u1ea7n","C. 3 l\u1ea7n","D. 4 l\u1ea7n"],"correct":"3","level":"3","hint":"","answer":"\u0110áp án \u0111úng: C. 3 l\u1ea7n<\/strong><\/span> Áp d\u1ee5ng v\u1edbi dãy: A = [11, 22, 33, 44, 55, 66, 77] (có 7 ph\u1ea7n t\u1eed, \u0111ã s\u1eafp x\u1ebfp t\u0103ng d\u1ea7n) C\u1ea7n tìm: 77 B\u01b0\u1edbc 1: Dãy có 7 ph\u1ea7n t\u1eed ⇒ v\u1ecb trí gi\u1eefa là ph\u1ea7n t\u1eed th\u1ee9 4 (v\u1ecb trí s\u1ed1 3 n\u1ebfu \u0111\u1ebfm t\u1eeb 0): A[3] = 44. So sánh: 77 > 44 ⇒ b\u1ecf n\u1eeda bên trái, ch\u1ec9 còn l\u1ea1i [55, 66, 77] B\u01b0\u1edbc 2: Dãy còn l\u1ea1i: [55, 66, 77] ⇒ ph\u1ea7n t\u1eed gi\u1eefa là 66. So sánh: 77 > 66 ⇒ b\u1ecf ti\u1ebfp bên trái, còn l\u1ea1i [77] B\u01b0\u1edbc 3: So sánh 77 v\u1edbi chính nó ⇒ trùng kh\u1edbp Nh\u01b0 v\u1eady, ph\u1ea3i so sánh 3 l\u1ea7n m\u1edbi tìm ra s\u1ed1 77:<\/p>","type":"choose","extra_type":"classic","time":"0","user_id":"151","test":"0","date":"2025-07-30 15:43:20","option_type":"txt","len":0}]}