บทความนี้แบ่งปันความแตกต่างของ Java ที่ใช้การค้นหาแบบไบนารีเพื่ออ้างอิง เนื้อหาเฉพาะมีดังนี้
การค้นหาแบบไบนารีปกติ:
ทบทวนการค้นหาไบนารีสามัญก่อน
หมายเหตุ: มีปัญหาเกี่ยวกับการค้นหาแบบไบนารี: เมื่อมีการทำซ้ำในอาร์เรย์เช่น {3, 3, 3, 3} เมื่อการค้นหาแบบไบนารี 3 การส่งคืนคือ arr [1] ซึ่งหมายถึงการค้นหาไบนารีจะไม่กลับตำแหน่ง 0 ของการเกิดขึ้นครั้งแรกของ 3
Public Class BinarySearch {public Static <t ขยายเปรียบเทียบได้ <? super t >> int search (t arr [], t value) {int left = 0; int right = arr.length - 1; ในขณะที่ (ซ้าย <= ขวา) {int mid = (ซ้าย & ขวา) + ((ซ้าย ^ ขวา) >> 1); if (arr [mid] .compareto (ค่า) == 0) {return mid; } อื่นถ้า (arr [mid] .compareto (ค่า)> 0) {ขวา = mid - 1; } else {left = mid + 1; }} return -1; } โมฆะคงที่สาธารณะหลัก (สตริง [] args) {จำนวนเต็ม [] arr = ใหม่จำนวนเต็ม [] {1, 3, 3, 6, 7, 9}; //-1 System.out.println (ค้นหา (arr, 0)); // 0 System.out.println (ค้นหา (arr, 1)); // 5 System.out.println (ค้นหา (arr, 9)); //-1 System.out.println (ค้นหา (arr, 10)); // 2 System.out.println (ค้นหา (arr, 3)); -ตัวแปร Bipartite: FindFirst Function
ในการค้นหาแบบไบนารีปกติค้นหาใน [ซ้าย ...... ขวา] ช่วงปิดซ้ายและด้านขวาปิด หากพบองค์ประกอบที่มีค่าก็จะถูกพิจารณาว่าจะพบ นี่ไม่ใช่กรณีในฟังก์ชั่น FindFirst นี้ ใน [ซ้าย ...... ขวา] ช่วงปิดด้านซ้ายปิดด้านขวาเมื่อพบองค์ประกอบที่มีค่าเท่ากับค่าจะถูกพบแทนที่จะเป็นขวา = กลาง-1 ให้ขวา = กลาง, ค้นหาต่อในการค้นหาใน [ซ้าย ...... ขวา] ช่วงปิดด้านซ้าย-ซ้าย ลูปออกเมื่อซ้าย == ในที่สุดก็ออกจาก
หลังจากออกจากลูปค่าอาจพบได้หรืออาจเป็นไปได้ว่าลูปจะไม่พบค่าหลังจากข้ามอาร์เรย์ที่สมบูรณ์และออกจากลูป
ดังนั้นหลังจากออกจากวงคุณต้องตัดสินว่าสถานการณ์คืออะไร
Public Class BinarySearch {public Static <t ขยายเปรียบเทียบได้ <? super t >> int findfirst (t arr [], ค่า t) {int left = 0; int right = arr.length - 1; // ออกเมื่อซ้าย> = ขวาสถานการณ์ "=" ที่นี่แตกต่างจากไบนารีในขณะที่ (ซ้าย <ขวา) {int mid = (ซ้าย + ขวา) >> 1; if (arr [mid] .compareto (ค่า) <0) {left = mid + 1; } else {right = mid; }} // หลังจากลูปข้างต้นถูกสำรวจ พบค่าหรือไม่? ยังไม่พบค่า? เพียงแค่ตัดสิน if (arr [ซ้าย] == ค่า) {return left; } else {return -1; }} โมฆะคงที่สาธารณะ (สตริง [] args) {จำนวนเต็ม [] arr = new Integer [] {1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 6, 7, 9}; //-1 system.out.println (findfirst (arr, 0)); // 0 System.out.println (findfirst (arr, 1)); // 12 system.out.println (findfirst (arr, 9)); //-1 system.out.println (findfirst (arr, 10)); // 1 system.out.println (findfirst (arr, 3)); -ตัวแปร bipartite: ฟังก์ชั่นน้อยลง
แนะนำ
ให้อาร์เรย์และค่าตัวแปรค้นหาหมายเลขจากอาร์เรย์ที่ใกล้เคียงกับค่ามากที่สุดและเล็กกว่าค่า ตัวอย่างเช่น arr = {11, 22, 22, 33, 33, 33, 44, 54} ค่า = 33. 22 ใกล้เคียงกับค่ามากที่สุดและเล็กกว่าค่า
ดังนั้นคำตอบคือ 2 (22 ในเครื่องหมายมุมล่างในอาร์เรย์ arr)
หากไม่พบตัวเลขที่เล็กกว่าค่าแล้วเอาต์พุต -1
สารละลาย
ใช้วิธีการค้นหาแบบไบนารี แต่ละครั้งใช้ arr [mid] เพื่อเปรียบเทียบกับค่า เล็กเท่ากับไปทางซ้ายเพื่อมองหามัน; ใหญ่ไปทางขวาเพื่อค้นหามัน คุณอาจไม่เข้าใจสถานการณ์ "เท่ากัน" ในประโยคก่อนหน้า การค้นหาไบนารีธรรมดาคือการค้นหาค่า arr [mid] == ในขณะที่ฟังก์ชั่นที่น้อยกว่าคือการหาตัวเลขที่เล็กกว่าค่าดังนั้นแม้ว่า arr [mid] == ค่าคุณต้องมองหาค่าที่เล็กกว่าทางด้านซ้าย
ตัวอย่าง
รหัส
Public Class BinarySearch {public Static <t ขยายเปรียบเทียบได้ <? super t >> int น้อยลง (t arr [], t value) {int left = 0; int right = arr.length - 1; // ออกในขณะที่ซ้าย> ขวา (ซ้าย <= ขวา) {int mid = (ซ้าย & ขวา) + ((ซ้าย ^ ขวา) >> 1); if (value.Compareto (arr [mid]) <= 0) {right = mid - 1; } else {left = mid + 1; }} กลับถูกต้อง; } โมฆะคงที่สาธารณะหลัก (สตริง [] args) {จำนวนเต็ม [] arrf = ใหม่จำนวนเต็ม [] {21, 23, 25, 25, 31, 34, 37, 39, 52, 63}; // 3 System.out.println (น้อยลง (arrf, 30)); -ตัวแปร bipartite: ฟังก์ชั่นที่มากขึ้น
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้ ฉันหวังว่ามันจะเป็นประโยชน์ต่อการเรียนรู้ของทุกคนและฉันหวังว่าทุกคนจะสนับสนุน wulin.com มากขึ้น