1. ภาพรวม
ในบทความนี้เราจะกล่าวถึงข้อดีของการค้นหาแบบไบนารีผ่านการค้นหาเชิงเส้นแบบง่ายและแนะนำการใช้งานใน Java
2. ต้องการการค้นหาที่มีประสิทธิภาพ
สมมติว่าเราอยู่ในธุรกิจขายไวน์และมีผู้ซื้อหลายล้านคนเข้าเยี่ยมชมแอปพลิเคชันของเราทุกวัน
ผ่านแอพของเราลูกค้าสามารถกรองสินค้าที่มีราคาต่ำกว่าnดอลลาร์เลือกขวดจากผลการค้นหาและเพิ่มลงในรถเข็นของเขา เรามีผู้ใช้หลายล้านคนที่กำลังมองหาไวน์ที่ จำกัด ราคาทุกๆวินาที ผลลัพธ์จะต้องรวดเร็ว
ในแบ็กเอนด์อัลกอริทึมของเราจะทำการค้นหาเชิงเส้นผ่านรายการไวน์ทั้งหมดโดยเปรียบเทียบขีด จำกัด ราคาที่ลูกค้าป้อนกับราคาไวน์ทุกขวดในรายการ
จากนั้นจะส่งคืนสินค้าที่มีราคาน้อยกว่าหรือเท่ากับขีด จำกัด ราคา นี้การค้นหาเชิงเส้นมีความซับซ้อนของเวลาO (n)
ซึ่งหมายความว่ายิ่งขวดไวน์ในระบบของเรามีจำนวนมากเท่าไหร่ก็ยิ่งต้องใช้เวลามากขึ้นเท่านั้น เวลาในการค้นหาจะเพิ่มขึ้นตามสัดส่วนของจำนวนรายการใหม่ที่เปิดตัว
ถ้าเราเริ่มต้นการประหยัดในรายการเรียงลำดับและค้นหารายการที่ใช้ค้นหา binary เราสามารถบรรลุความซับซ้อนของO (log n)
เมื่อใช้การค้นหาแบบไบนารีเวลาที่ใช้ในผลการค้นหาจะเพิ่มขึ้นตามขนาดของชุดข้อมูล แต่ไม่ได้ตามสัดส่วน
3. การค้นหาแบบไบนารี
พูดง่ายๆคืออัลกอริทึมจะเปรียบเทียบค่าคีย์กับองค์ประกอบตรงกลางของอาร์เรย์ หากไม่เท่ากันครึ่งหนึ่งที่ไม่สามารถเป็นส่วนหนึ่งของคีย์ได้จะถูกตัดออกและการค้นหาจะดำเนินต่อไปอีกครึ่งหนึ่งที่เหลือจนกว่าจะสำเร็จ
ข้อควรจำ - ประเด็นสำคัญในที่นี้คืออาร์เรย์ถูกจัดเรียงแล้ว
หากการค้นหาสิ้นสุดลงโดยที่ครึ่งที่เหลือว่างเปล่าแสดงว่าคีย์ไม่อยู่ในอาร์เรย์
3.1. อิมพีแอลซ้ำ
public int runBinarySearchIteratively( int[] sortedArray, int key, int low, int high) { int index = Integer.MAX_VALUE; while (low <= high) { int mid = (low + high) / 2; if (sortedArray[mid] key) { high = mid - 1; } else if (sortedArray[mid] == key) { index = mid; break; } } return index; }runBinarySearchIterativelyวิธีการใช้sortedArray , คีย์แอนด์ต่ำและสูงดัชนีของsortedArrayเป็นข้อโต้แย้ง เมื่อเมธอดทำงานเป็นครั้งแรกค่าต่ำดัชนีแรกของsortedArrayคือ 0 ในขณะที่ค่าสูงดัชนีสุดท้ายของsortedArrayจะเท่ากับความยาว - 1
กลางเป็นดัชนีกลางของsortedArray ตอนนี้ขั้นตอนวิธีทำงานในขณะที่วงเปรียบเทียบที่สำคัญที่มีค่าอาร์เรย์ของดัชนีกลางของsortedArray
3.2. Impl ซ้ำ
ตอนนี้เรามาดูการใช้งานแบบเรียกซ้ำแบบง่ายๆกัน:
public int runBinarySearchRecursively( int[] sortedArray, int key, int low, int high) { int middle = (low + high) / 2; if (high < low) { return -1; } if (key == sortedArray[middle]) { return middle; } else if (key < sortedArray[middle]) { return runBinarySearchRecursively( sortedArray, key, low, middle - 1); } else { return runBinarySearchRecursively( sortedArray, key, middle + 1, high); } } runBinarySearchRecursivelyวิธีการยอมรับsortedArray , กุญแจ, ต่ำและสูงดัชนีของsortedArray
3.3. การใช้อาร์เรย์ binarySearch ()
int index = Arrays.binarySearch(sortedArray, key); sortedArrayและคีย์intซึ่งจะถูกค้นหาในอาร์เรย์ของจำนวนเต็มจะถูกส่งผ่านไปยังเมธอดbinarySearchของคลาสJava Arrays
3.4. การใช้คอลเล็กชัน binarySearch ()
int index = Collections.binarySearch(sortedList, key); SortedList & จำนวนเต็มสำคัญซึ่งเป็นที่จะค้นหาในรายการของจำนวนเต็มวัตถุจะถูกส่งผ่านเป็นข้อโต้แย้งกับbinarySearchวิธีการ Java คอลเลกชันระดับ
3.5. ประสิทธิภาพ
ไม่ว่าจะใช้วิธีการแบบวนซ้ำหรือแบบวนซ้ำในการเขียนอัลกอริทึมนั้นส่วนใหญ่เป็นเรื่องของความชอบส่วนบุคคล แต่นี่คือบางประเด็นที่เราควรทราบ:
1. การเรียกซ้ำอาจช้าลงเนื่องจากมีค่าใช้จ่ายในการดูแลสแต็กและมักจะใช้หน่วยความจำมากขึ้น
2. Recursion ไม่stack-มิตร อาจทำให้เกิดStackOverflowExceptionเมื่อประมวลผลชุดข้อมูลขนาดใหญ่
3. การเรียกซ้ำจะเพิ่มความชัดเจนให้กับโค้ดเนื่องจากทำให้โค้ดสั้นลงเมื่อเทียบกับวิธีการวนซ้ำ
ตามหลักการแล้วการค้นหาแบบไบนารีจะทำการเปรียบเทียบจำนวนน้อยกว่าในทางตรงกันข้ามกับการค้นหาเชิงเส้นสำหรับค่าขนาดใหญ่ของ n สำหรับค่าที่น้อยกว่าของ n การค้นหาเชิงเส้นจะทำงานได้ดีกว่าการค้นหาแบบไบนารี
เราควรทราบว่าการวิเคราะห์นี้เป็นเชิงทฤษฎีและอาจแตกต่างกันไปขึ้นอยู่กับบริบท
นอกจากนี้ขั้นตอนวิธีการค้นหาแบบไบนารีต้องการชุดข้อมูลที่เรียงลำดับซึ่งมีค่าใช้จ่ายมากเกินไป หากเราใช้อัลกอริทึมการเรียงลำดับการผสานในการจัดเรียงข้อมูลความซับซ้อนเพิ่มเติมของn log nจะถูกเพิ่มเข้าไปในโค้ดของเรา
ก่อนอื่นเราต้องวิเคราะห์ข้อกำหนดของเราให้ดีจากนั้นจึงตัดสินใจว่าอัลกอริทึมการค้นหาใดที่จะเหมาะกับความต้องการของเรามากที่สุด
4. สรุป
บทช่วยสอนนี้แสดงให้เห็นถึงการใช้อัลกอริธึมการค้นหาแบบไบนารีและสถานการณ์ที่ควรใช้แทนการค้นหาเชิงเส้น
โปรดดูรหัสสำหรับการสอนบน GitHub