Thuật toán tìm kiếm nhị phân ( dễ )

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 cơ bản

{"common":{"save":0,"post_id":"9790","level":1,"total":10,"point":10,"point_extra":0},"segment":[{"id":"11739","post_id":"9790","mon_id":"1160119","chapter_id":"1160137","question":"Thu\u1eadt toán tìm ki\u1ebfm nh\u1ecb phân là gì?<\/p>","options":["A. Th\u1ef1c hi\u1ec7n tìm ki\u1ebfm trên danh sách \u0111ã s\u1eafp x\u1ebfp t\u1eeb v\u1ecb trí \u1edf gi\u1eefa danh sách","B. Th\u1ef1c hi\u1ec7n tìm ki\u1ebfm trên danh sách \u0111ã s\u1eafp x\u1ebfp t\u1eeb v\u1ecb trí \u1edf \u0111\u1ea7u danh sách","C. Th\u1ef1c hi\u1ec7n tìm ki\u1ebfm trên danh sách \u0111ã s\u1eafp x\u1ebfp t\u1eeb v\u1ecb trí \u1edf cu\u1ed1i danh sách","D. Th\u1ef1c hi\u1ec7n tìm ki\u1ebfm trên danh sách không s\u1eafp x\u1ebfp t\u1eeb v\u1ecb trí \u1edf gi\u1eefa danh sách"],"correct":"1","level":"1","hint":"","answer":"\u0110áp án \u0111úng: A. Th\u1ef1c hi\u1ec7n tìm ki\u1ebfm trên danh sách \u0111ã s\u1eafp x\u1ebfp t\u1eeb v\u1ecb trí \u1edf gi\u1eefa danh sách<\/strong><\/span> Thu\u1eadt toán tìm ki\u1ebfm nh\u1ecb phân (còn g\u1ecdi là tìm ki\u1ebfm chia \u0111ôi) là cách tìm ki\u1ebfm r\u1ea5t nhanh trên danh sách \u0111ã \u0111\u01b0\u1ee3c s\u1eafp x\u1ebfp tr\u01b0\u1edbc (t\u0103ng d\u1ea7n ho\u1eb7c gi\u1ea3m d\u1ea7n). Cách ho\u1ea1t \u0111\u1ed9ng: Ch\u1ecdn v\u1ecb trí \u1edf gi\u1eefa danh sách \u0111\u1ec3 so sánh v\u1edbi giá tr\u1ecb c\u1ea7n tìm; N\u1ebfu \u0111úng, d\u1eebng l\u1ea1i; N\u1ebfu giá tr\u1ecb c\u1ea7n tìm nh\u1ecf h\u01a1n, ch\u1ec9 xét ti\u1ebfp n\u1eeda bên trái; N\u1ebfu giá tr\u1ecb c\u1ea7n tìm l\u1edbn h\u01a1n, ch\u1ec9 xét ti\u1ebfp n\u1eeda bên ph\u1ea3i; L\u1eb7p l\u1ea1i vi\u1ec7c chia \u0111ôi cho \u0111\u1ebfn khi tìm th\u1ea5y ho\u1eb7c h\u1ebft danh sách.<\/p>","type":"choose","extra_type":"classic","time":"0","user_id":"151","test":"0","date":"2025-07-30 14:24:23","option_type":"txt","len":3},{"id":"11740","post_id":"9790","mon_id":"1160119","chapter_id":"1160137","question":"T\u01b0 t\u01b0\u1edfng c\u1ee7a thu\u1eadt toán tìm ki\u1ebfm nh\u1ecb phân là gì?<\/p>","options":["A. Tìm ki\u1ebfm d\u1ef1a vào cây tìm ki\u1ebfm.","B. Tìm ki\u1ebfm t\u1eeb \u0111\u1ea7u \u0111\u1ebfn cu\u1ed1i dãy.","C. T\u1ea1i m\u1ed7i b\u01b0\u1edbc ti\u1ebfn hành so sánh X v\u1edbi ph\u1ea7n t\u1eed gi\u1eefa c\u1ee7a dãy. D\u1ef1a vào b\u01b0\u1edbc so sánh này quy\u1ebft \u0111\u1ecbnh tìm ki\u1ebfm \u1edf n\u1eeda \u0111\u1ea7u hay \u1edf n\u1eeda sau c\u1ee7a danh sách.","D. So sánh X l\u1ea7n l\u01b0\u1ee3t v\u1edbi các ph\u1ea7n t\u1eed a1, a2, …, an."],"correct":"3","level":"1","hint":"","answer":"\u0110áp án \u0111úng: C. T\u1ea1i m\u1ed7i b\u01b0\u1edbc ti\u1ebfn hành so sánh X v\u1edbi ph\u1ea7n t\u1eed gi\u1eefa c\u1ee7a dãy. D\u1ef1a vào b\u01b0\u1edbc so sánh này quy\u1ebft \u0111\u1ecbnh tìm<\/strong><\/span> ki\u1ebfm \u1edf n\u1eeda \u0111\u1ea7u hay \u1edf n\u1eeda sau c\u1ee7a danh sách.<\/strong><\/span> Thu\u1eadt toán tìm ki\u1ebfm nh\u1ecb phân (còn g\u1ecdi là Binary Search) là cách tìm ki\u1ebfm r\u1ea5t nhanh, nh\u01b0ng ch\u1ec9 áp d\u1ee5ng \u0111\u01b0\u1ee3c v\u1edbi dãy s\u1ed1 \u0111ã \u0111\u01b0\u1ee3c s\u1eafp x\u1ebfp (t\u0103ng d\u1ea7n ho\u1eb7c gi\u1ea3m d\u1ea7n). Nguyên t\u1eafc ho\u1ea1t \u0111\u1ed9ng: Xác \u0111\u1ecbnh ph\u1ea7n t\u1eed \u1edf gi\u1eefa dãy; So sánh X (s\u1ed1 c\u1ea7n tìm) v\u1edbi ph\u1ea7n t\u1eed gi\u1eefa: N\u1ebfu X b\u1eb1ng ph\u1ea7n t\u1eed gi\u1eefa → Tìm th\u1ea5y, N\u1ebfu X nh\u1ecf h\u01a1n → Tìm trong n\u1eeda \u0111\u1ea7u c\u1ee7a dãy, N\u1ebfu X l\u1edbn h\u01a1n → Tìm trong n\u1eeda sau c\u1ee7a dãy; L\u1eb7p l\u1ea1i các b\u01b0\u1edbc trên v\u1edbi ph\u1ea7n dãy nh\u1ecf h\u01a1n cho \u0111\u1ebfn khi: Tìm \u0111\u01b0\u1ee3c X, ho\u1eb7c Không còn ph\u1ea7n t\u1eed nào \u0111\u1ec3 tìm (k\u1ebft lu\u1eadn là không có X trong dãy).<\/p>","type":"choose","extra_type":"classic","time":"0","user_id":"151","test":"0","date":"2025-07-30 14:25:27","option_type":"txt","len":3},{"id":"11741","post_id":"9790","mon_id":"1160119","chapter_id":"1160137","question":"Trong thu\u1eadt toán tìm ki\u1ebfm nh\u1ecb phân thì vùng tìm ki\u1ebfm lúc ban \u0111\u1ea7u là gì?<\/p>","options":["A. N\u1eeda \u0111\u1ea7u danh sách.","B. N\u1eeda \u0111\u1ea7u danh sách.","C. Toàn b\u1ed9 danh sách.","D. \u0110áp án khác."],"correct":"3","level":"1","hint":"","answer":"\u0110áp án \u0111úng: C. Toàn b\u1ed9 danh sách.<\/strong><\/span> Khi b\u1eaft \u0111\u1ea7u tìm, thu\u1eadt toán xét toàn b\u1ed9 danh sách (t\u1eeb ph\u1ea7n t\u1eed \u0111\u1ea7u \u0111\u1ebfn ph\u1ea7n t\u1eed cu\u1ed1i), sau \u0111ó: Chia \u0111ôi danh sách; So sánh giá tr\u1ecb \u1edf gi\u1eefa v\u1edbi giá tr\u1ecb c\u1ea7n tìm; D\u1ef1a vào k\u1ebft qu\u1ea3 so sánh, thu h\u1eb9p vùng tìm ki\u1ebfm còn m\u1ed9t n\u1eeda: N\u1ebfu nh\u1ecf h\u01a1n → tìm \u1edf n\u1eeda bên ph\u1ea3i, N\u1ebfu l\u1edbn h\u01a1n → tìm \u1edf n\u1eeda bên trái Nh\u01b0ng ban \u0111\u1ea7u, ch\u01b0a bi\u1ebft nó n\u1eb1m \u1edf \u0111âu, nên ph\u1ea3i xét c\u1ea3 danh sách.<\/p>","type":"choose","extra_type":"classic","time":"0","user_id":"151","test":"0","date":"2025-07-30 14:52:59","option_type":"txt","len":2}]}