วิธีการเขียนอัลกอริทึมการค้นหาแบบไบนารีใน Java
คอมพิวเตอร์ไม่ค้นหาสิ่งของเหมือนที่มนุษย์ทำ ในขณะที่มนุษย์สามารถเปลี่ยนวิธีการในการค้นหาบางสิ่งได้ คอมพิวเตอร์จำเป็นต้องได้รับคำแนะนำเฉพาะเกี่ยวกับการค้นหารายการใดรายการหนึ่ง นั่นคือสิ่งที่อัลกอริธึมมาตรฐานมีประโยชน์
การค้นหาไบนารีเป็นตัวอย่างของอัลกอริธึมมาตรฐาน ใช้เพื่อค้นหาองค์ประกอบในอาร์เรย์ของรายการ ในคู่มือนี้ เราจะพูดถึงการค้นหาไบนารีคืออะไร วิธีทำงาน และวิธีที่คุณสามารถนำไปใช้ใน Java เราจะพูดถึงสองตัวอย่างของการค้นหาแบบไบนารี:แบบหนึ่งใช้วิธีการแบบเรียกซ้ำ และอีกแบบใช้วิธีการแบบวนซ้ำ
เริ่มกันเลย!
การค้นหาแบบไบนารีคืออะไร
การค้นหาแบบไบนารีคืออัลกอริธึมการค้นหาที่กำหนดตำแหน่งขององค์ประกอบในอาร์เรย์ที่เรียงลำดับ
การค้นหาไบนารีเริ่มต้นด้วยการแบ่งรายการออกเป็นสองส่วน การค้นหาจะเปรียบเทียบตัวเลขตรงกลางกับตัวเลขที่อัลกอริทึมกำลังค้นหา
ถ้าตัวเลขน้อยกว่าตัวเลขตรงกลาง กระบวนการนี้จะทำซ้ำสำหรับครึ่งล่างของรายการ มิฉะนั้น กระบวนการนี้จะทำซ้ำสำหรับครึ่งบนของรายการ
การค้นหาแบบไบนารีมีประสิทธิภาพมากกว่าการค้นหาเชิงเส้น ซึ่งเป็นการค้นหาทั่วไปอีกประเภทหนึ่ง เนื่องจากทุกครั้งที่อัลกอริทึมค้นหารายการ จะลดจำนวนรายการที่ต้องการค้นหาลงเป็นสองเท่า
การค้นหาแบบไบนารีสามารถดำเนินการได้เฉพาะในรายการที่เรียงลำดับแล้วเท่านั้น ซึ่งหมายความว่าหากคุณยังไม่มีรายการที่จัดเรียง คุณจะต้องจัดเรียงโดยใช้อัลกอริทึมการจัดเรียงก่อนที่จะดำเนินการค้นหาแบบไบนารี
81% ของผู้เข้าร่วมกล่าวว่าพวกเขารู้สึกมั่นใจมากขึ้นเกี่ยวกับโอกาสในการทำงานด้านเทคโนโลยีหลังจากเข้าร่วม bootcamp จับคู่กับ Bootcamp วันนี้
ผู้สำเร็จการศึกษาจากหลักสูตร bootcamp โดยเฉลี่ยใช้เวลาน้อยกว่าหกเดือนในการเปลี่ยนอาชีพ ตั้งแต่เริ่มต้น bootcamp ไปจนถึงหางานแรก
การค้นหาไบนารีทำงานอย่างไร
การค้นหาไบนารีสามารถทำได้สองวิธี:วนซ้ำหรือวนซ้ำ
การค้นหาไบนารีแบบวนซ้ำเป็นการค้นหาแบบวนซ้ำเพื่อค้นหารายการในรายการ การค้นหาไบนารีแบบเรียกซ้ำใช้ฟังก์ชันที่เรียกตัวเองซ้ำแล้วซ้ำอีกเพื่อค้นหารายการในรายการ การค้นหาไบนารีแบบเรียกซ้ำใช้วิธีการแบ่งและพิชิตเพื่อค้นหารายการ
คุณสามารถเรียนรู้เพิ่มเติมเกี่ยวกับการเรียกซ้ำในคู่มือการเรียกซ้ำของ Java
อัลกอริทึมทั่วไปสำหรับการดำเนินการค้นหาแบบไบนารีจะเหมือนกันไม่ว่าคุณจะตัดสินใจใช้แนวทางใด
พิจารณารายการต่อไปนี้:
| 6 | 7 | 8 | 9 | 10 |
เราจะค้นหาหมายเลข 7 ในรายการของเรา ในการเริ่มต้น เราจะตั้งค่าตัวชี้สองตัวซึ่งแสดงถึงตำแหน่งต่ำสุดและสูงสุดในรายการของเรา:
| ต่ำ | | | | สูง |
| 6 | 7 | 8 | 9 | 10 |
ต่อไปเราต้องหาองค์ประกอบกลางในอาร์เรย์ของเรา เราสามารถทำได้โดยใช้สูตร:(ต่ำ + สูง) / 2 ในกรณีนี้องค์ประกอบตรงกลางคือ 8
อัลกอริทึมของเราจะเปรียบเทียบว่าองค์ประกอบตรงกลางเท่ากับองค์ประกอบที่เรากำลังค้นหาหรือไม่ หากตัวเลขเท่ากัน การค้นหาของเราจะหยุดลง เรากำลังมองหาหมายเลข 7 ซึ่งไม่เท่ากับ 8 ดังนั้นการค้นหาของเราจึงดำเนินต่อไป
อัลกอริทึมของเราจะเปรียบเทียบว่าจำนวนที่เรากำลังค้นหานั้นมากกว่าตัวเลขตรงกลางหรือไม่ ถ้ามากกว่านั้น การค้นหาของเราจะเริ่มต้นใหม่อีกครั้งในครึ่งบนของรายการ ทำได้โดยการตั้งค่า low ให้เท่ากับ low =middle_number + 1 มิฉะนั้น การค้นหาจะเริ่มต้นอีกครั้งที่ครึ่งล่างของรายการ
7 (ตัวเลขที่เรากำลังค้นหา) ไม่เกิน 8 (ตัวเลขกลาง) ซึ่งหมายความว่าอัลกอริทึมของเรากำลังค้นหาในช่วงครึ่งล่างของรายการ เราทำสิ่งนี้โดยตั้งค่า “สูง” เป็น high =middle_number – 1
| ต่ำ | กลาง | สูง | | |
| 6 | 7 | 8 | 9 | 10 |
ตอนนี้ อัลกอริทึมของเรากำลังจะทำการค้นหาซ้ำ เราจะเปรียบเทียบตัวเลขตรงกลาง 7 กับตัวเลขที่เรากำลังค้นหา เรากำลังมองหาหมายเลข 7 ดังนั้นอัลกอริทึมการค้นหาของเราจึงหยุดลง เราพบตำแหน่ง 7 ในรายการของเราแล้ว!
วิธีการใช้ Java Binary Search
เราเลิกใช้ทฤษฎีนี้แล้ว ตอนนี้เหลือเพียงดำเนินการค้นหาของเรา เป็นสิ่งหนึ่งที่ต้องผ่านและค้นหารายการด้วยตัวเราเอง การเขียนโค้ดอัลกอริธึมที่ทำการค้นหาเราเป็นอีกสิ่งหนึ่งที่ทั้งหมด
เราจะเริ่มต้นด้วยการเขียนโปรแกรมที่ใช้การค้นหาไบนารี Java โดยใช้วิธีการวนซ้ำ
วิธีการทำซ้ำ
มากำหนดฟังก์ชันที่เรียกว่า searchItems ซึ่งค้นหาผ่านรายการของเรา:
class BinarySearch {
int searchItems(int array[], int searchingFor, int low, int high) {
while (low <= high) {
int middle = low + (high - low) / 2;
if (array[middle] == searchingFor) {
return middle;
} else if (array[middle] < searchingFor) {
low = middle + 1;
} else {
high = middle - 1;
}
}
return -1;
}
}
ฟังก์ชันนี้จะค้นหารายการของเราโดยใช้การค้นหาแบบไบนารี
ฟังก์ชันของเรายอมรับพารามิเตอร์สี่ตัว ได้แก่ รายการที่เราต้องการค้นหา (อาร์เรย์) รายการที่เรากำลังค้นหา (กำลังค้นหา) ตัวเลขต่ำ (ต่ำ) และตัวเลขสูง (สูง)
ภายในฟังก์ชันของเราเราได้ประกาศ while loop แม้ว่าค่าของ "ต่ำ" จะน้อยกว่าหรือเท่ากับ "สูง" การวนซ้ำจะดำเนินการ
วง while ของเราเริ่มต้นด้วยการคำนวณจำนวนตรงกลาง จากนั้นจะตรวจสอบเพื่อดูว่าค่าที่ตำแหน่งนั้นเท่ากับค่าที่เรากำลังค้นหาหรือไม่
หากตัวเลขเหล่านั้นเท่ากัน ค่านั้นจะถูกส่งคืนไปยังโปรแกรมหลักของเรา หากไม่เป็นเช่นนั้น โปรแกรมของเราจะตรวจสอบว่าค่าที่ตำแหน่งตรงกลางน้อยกว่าค่าที่เรากำลังค้นหาหรือไม่ ถ้าใช่ ค่าต่ำใหม่จะถูกตั้งค่า
มิฉะนั้น ค่าสูงใหม่จะถูกตั้งค่าเพื่อให้รายการของเราสามารถค้นหาได้อีกครั้งในครึ่งบนของรายการ
หากไม่พบรายการของเรา -1 จะถูกส่งคืน เราจะใช้สิ่งนี้เพื่อบอกโปรแกรมหลักของเราว่าไม่พบรายการในหนึ่งนาที
รหัสของเราไม่ได้ทำอะไรเลยเพราะเรายังไม่ได้เขียนโปรแกรมหลักของเรา เพิ่มโค้ดต่อไปนี้ใต้ searchItems() ฟังก์ชันในคลาส BinarySearch ของคุณ:
public static void main(String args[]) {
BinarySearch newSearch = new BinarySearch();
int listToSearch[] = { 6, 7, 8, 9, 10 };
int listLength = listToSearch.length;
int numberToFind = 7;
int findNumber = newSearch.searchItems(listToSearch, numberToFind, 0, listLength - 1);
if (findNumber != -1) {
System.out.println(numberToFind + " was found at index position " + findNumber + ".");
} else {
System.out.println(numberToFind + " was not found in the list.");
}
} เรียกใช้โค้ดของเราแล้วดูว่าเกิดอะไรขึ้น:
7 was found at index position 1. We've found the position of our number!
โปรแกรมหลักของเราเริ่มต้นด้วยการเริ่มต้นอินสแตนซ์ของคลาส BinarySearch เราใช้สิ่งนี้เพื่อเริ่มการค้นหาของเราในโปรแกรม จากนั้นเราจะกำหนดตัวแปรสามตัว:
- listToSearch:รายการที่เราต้องการค้นหา
- listLength:ความยาวของรายการ
- numberToFind:หมายเลขที่เรากำลังมองหาในรายการ
เมื่อเรากำหนดตัวแปรเหล่านี้แล้ว เราจะใช้ searchItems() ฟังก์ชั่นที่เราประกาศไว้ก่อนหน้านี้เพื่อค้นหาตัวเลขในรายการของเรา เรากำหนดค่าที่ฟังก์ชันนี้จะส่งคืนให้กับตัวแปร "findNumber"
หาก findNumber ไม่เท่ากับ -1 ซึ่งหมายความว่าพบหมายเลขของเราแล้ว ตำแหน่งดัชนีของรายการที่เรากำลังค้นหาจะถูกพิมพ์ไปยังคอนโซล มิฉะนั้น จะมีการพิมพ์ข้อความไปที่คอนโซลเพื่อแจ้งว่าไม่พบหมายเลข
วิธีการแบบเรียกซ้ำ
สามารถใช้วิธีการแบบเรียกซ้ำเพื่อใช้การค้นหาแบบไบนารี นี่คือที่ที่คุณเขียนฟังก์ชันที่เรียกตัวเองจนกว่าจะพบรายการที่ระบุ
เริ่มต้นด้วยการกำหนดฟังก์ชันที่ทำการค้นหาไบนารีของเราแบบเรียกซ้ำ:
class BinarySearch {
int searchItems(int array[], int searchingFor, int low, int high) {
if (high >= low) {
int middle = low + (high - low) / 2;
if (array[middle] == searchingFor) {
return middle;
} else if (array[middle] < searchingFor) {
searchItems(array, searchingFor, middle + 1, high);
} else {
searchItems(array, searchingFor, low, middle - 1);
}
}
return -1;
}
}
ฟังก์ชันนี้ใช้การค้นหาไบนารีของเราในทางที่ต่างออกไป แทนที่จะใช้ while loop เราใช้ if คำสั่งตรวจสอบว่าจำนวนสูงเท่ากับหรือน้อยกว่าจำนวนที่ต่ำ
หากข้อความนี้ประเมินว่าเป็นจริง การค้นหาของเราจะเริ่มต้นขึ้น มิฉะนั้น -1 จะถูกส่งกลับ ซึ่งบอกโปรแกรมของเราว่าไม่พบรายการที่ระบุในรายการ
ภายใน if . ของเรา คำสั่งเราตรวจสอบว่าค่าของตัวเลขตรงกลางเท่ากับค่าที่เรากำลังค้นหาหรือไม่ ถ้าใช่ เราจะคืนหมายเลขนั้นไปที่โปรแกรมหลักของเรา
หากข้อความนี้ไม่ประเมินว่าเป็นจริง โปรแกรมของเราจะตรวจสอบเพื่อดูว่าตัวเลขที่อยู่ตรงกลางน้อยกว่าตัวเลขที่เรากำลังค้นหาหรือไม่ ถ้าใช่ searchItems() เมธอดจะถูกรันอีกครั้ง แต่คราวนี้จำนวนที่ต่ำของเราจะเท่ากับหนึ่งที่มากกว่าจำนวนตรงกลางของเรา สิ่งนี้จะแบ่งจำนวนรายการที่เราต้องการค้นหาออกเป็นสองส่วน
มิฉะนั้น searchItems() ถูกเรียกใช้อีกครั้งและค่าของจำนวนสูงสุดจะเท่ากับจำนวนตรงกลางลบหนึ่ง ซึ่งหมายความว่าเราสามารถปรับแต่งการค้นหาของเราได้เพียงครึ่งซ้ายของรายการของเรา
เราสามารถใช้ฟังก์ชันหลักเดียวกันกับที่เราเขียนไว้ก่อนหน้านี้เพื่อทดสอบโค้ดของเรา มาดูกันว่าจะเกิดอะไรขึ้นเมื่อเรารันโค้ดของเรา:
7 was found at index position 1.
พบสินค้าของเราอีกแล้ว! ครั้งนี้ เราใช้วิธีการแบบเรียกซ้ำเพื่อค้นหาหมายเลขของเราแทนการวนซ้ำ
การวิเคราะห์ความซับซ้อน
อัลกอริธึมการค้นหาแบบไบนารีมีความซับซ้อนของตัวพิมพ์ที่ดีที่สุดของ O(1) สิ่งนี้จะเกิดขึ้นเมื่อรายการแรกที่เปรียบเทียบโดยอัลกอริทึมคือรายการที่มีการค้นหา
อัลกอริธึมการค้นหาแบบไบนารีมีความซับซ้อนของตัวพิมพ์ใหญ่และตัวพิมพ์เล็กโดยเฉลี่ยของ O(log n) ซึ่งหมายความว่า ในกรณีส่วนใหญ่ และในกรณีที่เลวร้ายที่สุด ความเร็วของอัลกอริทึมจะช้าลงตามลอการิทึม ขึ้นอยู่กับจำนวนรายการที่ต้องทำการค้นหา
บทสรุป
การค้นหาไบนารีใช้เพื่อค้นหาตำแหน่งขององค์ประกอบในรายการที่เรียงลำดับ การค้นหาแบบไบนารีจะเปรียบเทียบรายการที่อยู่ตรงกลางส่วนของอาร์เรย์กับตัวเลขที่อัลกอริทึมกำลังค้นหา
การค้นหาไบนารีมีประสิทธิภาพมากกว่าการค้นหาเชิงเส้น เนื่องจากทุกครั้งที่ทำการค้นหา จำนวนค่าที่ต้องค้นหาจะถูกหารด้วยสองค่า
ตอนนี้คุณพร้อมแล้วที่จะใช้การค้นหาไบนารีใน Java เหมือนกับโปรแกรมเมอร์ผู้เชี่ยวชาญ
