Binary Search Java: คู่มือการ Implement แบบ Recursive และ Iterative

วิธีเขียน Binary Search Algorithm ใน Java

คอมพิวเตอร์ไม่ค้นหา items เหมือนมนุษย์ ในขณะที่มนุษย์สามารถเปลี่ยนแปลงวิธีการหาสิ่งของได้ คอมพิวเตอร์ต้องได้รับคำสั่งเฉพาะเกี่ยวกับวิธี locate item เฉพาะ นี่คือที่มาของ standard algorithms

Binary searches เป็นตัวอย่างของ standard algorithm พวกมันใช้หา element ใน sorted array ของ items ในคู่มือนี้ เราจะพูดถึงว่า binary searches คืออะไร ทำงานอย่างไร และคุณสามารถ implement พวกมันใน Java ได้อย่างไร เราจะเดินทางผ่านสองตัวอย่างของ binary search: หนึ่งใช้ recursive approach และอีกหนึ่งใช้ iterative approach

มาเริ่มกัน!

Binary Search คืออะไร?

Binary search เป็น search algorithm ที่ locate ตำแหน่งของ element ใน sorted array

Binary searches เริ่มด้วยการแบ่ง list เป็นครึ่ง สาย search จะเปรียบเทียบ middle number กับตัวเลขที่ algorithm กำลังค้นหา

หากตัวเลขน้อยกว่า middle number กระบวนการนี้จะซ้ำสำหรับ lower half ของ list มิฉะนั้น กระบวนการนี้จะซ้ำสำหรับ upper half ของ list

Binary searches มีประสิทธิภาพมากกว่า linear searches อีกประเภท search ที่พบบ่อย เพราะทุกครั้งที่ algorithm หา item มันลดจำนวน items ที่ต้อง search ผ่านลงโดย factor of two

Binary searches สามารถ execute ได้เฉพาะบน sorted list ของ items นี่หมายความว่าหากคุณยังไม่มี sorted list คุณจะต้อง sort มันโดยใช้ sorting algorithm ก่อน run binary search

81% ของผู้เข้าร่วมระบุว่ารู้สึกมั่นใจมากขึ้นเกี่ยวกับโอกาสงานทางเทคโนโลยีหลังจากเข้าร่วมบูทแคมป์ ได้รับการจับคู่กับบูทแคมป์วันนี้

นักศึกษาจบบูทแคมป์เฉลี่ยใช้เวลาน้อยกว่า 6 เดือนในการเปลี่ยนอาชีพ ตั้งแต่เริ่มบูทแคมป์จนหางานแรก

Binary Searches ทำงานอย่างไร?

Binary searches สามารถ implement ได้สองวิธี: iteratively หรือ recursively

Iterative binary search คือที่ใช้ loops เพื่อ search item ใน list Recursive binary search ใช้ฟังก์ชันที่เรียกตัวมันเองซ้ำๆ เพื่อหา item ใน list Recursive binary searches ใช้ divide and conquer approach เพื่อหา item

คุณสามารถเรียนรู้เพิ่มเติมเกี่ยวกับ recursion ในคู่มือของเราเกี่ยวกับ Java recursion

อัลกอริธึมทั่วไปสำหรับ implement binary search เหมือนกันไม่ว่า Sie จะเลือกแนวทางไหน

พิจารณารายการต่อไปนี้:

เราจะ search หาตัวเลข 7 ในรายการของเรา เริ่มต้น เราจะตั้งค่า pointers สองตัวซึ่งแทน lowest และ highest positions ในรายการของเรา:

ต่อไป เราต้องหา middle element ใน array ของเรา เราสามารถทำได้โดยใช้สูตร: (low + high) / 2 ในกรณีนี้ middle element คือ 8

Algorithm ของเราจะเปรียบเทียบว่า middle element เท่ากับตัวเลขที่เราค้นหาหรือไม่ หากตัวเลขเท่ากัน search ของเราสามารถหยุดได้ เรากำลังหาตัวเลข 7 ซึ่งไม่เท่ากับ 8 ดังนั้น search ของเราดำเนินต่อ

Algorithm ของเราเปรียบเทียบว่าตัวเลขที่เราค้นหามากกว่า middle number หรือไม่ หากมากกว่า search ของเราจะเริ่มใหม่ทั้งหมดบน upper half ของรายการของเรา ทำได้โดยการตั้ง low ให้เท่ากับ low = middle_number + 1 มิฉะนั้น search จะเริ่มใหม่บน lower half ของรายการของเรา

7 (ตัวเลขที่เราค้นหา) ไม่มากกว่า 8 (middle number) นี่หมายความว่า algorithm ของเราจะ search ผ่าน lower half ของรายการของเรา เราทำได้โดยการตั้งค่า "high" ให้ high = middle_number - 1

ตอนนี้ algorithm ของเราจะ repeat search ของเรา เราจะเปรียบเทียบ middle number, 7 กับตัวเลขที่เราค้นหา เรากำลังหาตัวเลข 7 ดังนั้น search algorithm ของเราหยุด เราพบตำแหน่งของ 7 ในรายการของเราแล้ว!

วิธี Implement Java Binary Search

เราเสร็จ theory แล้ว ดังนั้นสิ่งที่เหลือคือ implement search ของเรา มันเป็นอย่างหนึ่งที่จะไป search list ด้วยตัวเราเอง มันเป็นอีกอย่างที่จะเขียน algorithm ที่ทำ search ให้เรา

เราจะเริ่มเขียนโปรแกรมที่ implement Java binary search โดยใช้ iterative method

Iterative Method

มา define ฟังก์ชันชื่อ searchItems ซึ่ง search ผ่านรายการ items ของเรา:

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; } }

ฟังก์ชันนี้ search ผ่านรายการ items ของเราโดยใช้ binary search

ฟังก์ชันของเรารับสี่พารามิเตอร์: รายการที่เราต้องการ search (array), item ที่เราค้นหา (searchingFor), ตัวเลข low (low), และตัวเลข high (high)

ภายในฟังก์ชันของเรา เรา declare while loop ขณะที่ค่า "low" น้อยกว่าหรือเท่ากับ "high" ลูปจะ execute

While loop ของเราเริ่มด้วยการคำนวณ middle number มันจากนั้นตรวจสอบว่าค่าที่ตำแหน่งนั้นเท่ากับตัวเลขที่เราค้นหาหรือไม่

หากตัวเลขเหล่านั้นเท่ากัน ค่านั้นจะถูกคืนไปยัง main program ของเรา หากไม่ โปรแกรมของเราจะตรวจสอบว่าค่าที่ตำแหน่งกลางน้อยกว่าตัวเลขที่เราค้นหาหรือไม่ หากใช่ ค่า low ใหม่จะถูกตั้ง

มิฉะนั้น ค่า high ใหม่จะถูกตั้ง เพื่อรายการของเราสามารถ search อีกครั้งใน upper half ของรายการ

หาก item ของเราไม่สามารถหาได้ -1 จะถูกคืน เราจะใช้สิ่งนี้บอก main program ของเราว่ารายการ item ไม่สามารถหาได้ในหนึ่งนาที

โค้ดของเรายังไม่ทำอะไร เพราะเรายังไม่เขียน main program เพิ่มโค้ดต่อไปนี้ด้านล่างฟังก์ชัน 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."); } }

มา run โค้ดของเราและดูว่าจะเกิดอะไร:

7 was found at index position 1. We've found the position of our number!

Main program ของเราเริ่มด้วยการ initialize instance ของคลาส BinarySearch เราใช้สิ่งนี้เริ่ม search ของเราในภายหลังในโปรแกรม เราจึงกำหนดตัวแปรสามตัว:

• listToSearch: รายการที่เราต้องการ search ผ่าน
• listLength: ความยาวของรายการ
• numberToFind: ตัวเลขที่เรากำลังหาในรายการ

เมื่อเรา define ตัวแปรเหล่านี้แล้ว เราใช้ฟังก์ชัน searchItems() ที่เรา declare ก่อนหน้านี้เพื่อหาตัวเลขในรายการของเรา เรากำหนดค่าที่ฟังก์ชันนี้คืนให้ตัวแปร "findNumber"

หาก findNumber ไม่เท่ากับ -1 — ซึ่งหมายความว่าตัวเลขของเราถูกหาแล้ว — index position ของ item ที่เรากำลังค้นหาจะถูกพิมพ์ไปที่ console มิฉะนั้น ข้อความจะถูกพิมพ์ไปที่ console บอกเราว่าตัวเลขไม่สามารถหาได้

Recursive Method

แนวทาง recursive สามารถใช้ implement binary search ได้ นี่คือที่คุณเขียนฟังก์ชันที่เรียกตัวมันเองจนกว่าจะพบ item ที่ระบุ

มาเริ่ม define ฟังก์ชันที่ทำ binary search แบบ recursive:

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; } }

ฟังก์ชันนี้ implement binary search ของเราในวิธีต่างออกไป แทนที่จะใช้ while loop เราใช้ if statement ตรวจสอบว่าตัวเลข high เท่ากับหรือน้อยกว่าตัวเลข low

หาก statement นี้ evaluate เป็น true search ของเราเริ่ม มิฉะนั้น -1 จะถูกคืน ซึ่งบอกโปรแกรมของเราว่า specified item ไม่สามารถหาได้ในรายการ

ภายใน if statement ของเรา เราตรวจสอบว่าค่าของ middle number เท่ากับตัวเลขที่เราค้นหาหรือไม่ หากใช่ เราคืนตัวเลขนั้นไปยัง main program ของเรา

หาก statement นี้ไม่ evaluate เป็น true โปรแกรมของเราตรวจสอบว่าตัวเลขในตำแหน่งกลางน้อยกว่าตัวเลขที่เราค้นหาหรือไม่ หากใช่ เมธอด searchItems() จะ run อีกครั้ง แตคราวนี้ low number ของเราจะเท่ากับหนึ่งมากกว่า middle number ของเรา นี่แบ่งจำนวน items ที่รายการของเราต้อง search ผ่านลงสอง

มิฉะนั้น searchItems() run อีกครั้ง และค่าของ highest number ถูกทำให้เท่ากับ middle number minus one นี่หมายความว่าเราสามารถปรับปรุง search ของเราเฉพาะ left half ของรายการของเรา

เราสามารถใช้ main function เดียวกันที่เราเขียนก่อนหน้านี้เพื่อทดสอบโค้ดของเรา มาดูว่าจะเกิดอะไรเมื่อเรา run โค้ดของเรา:

7 was found at index position 1.

Item ของเราถูกหาอีกครั้ง! คราวนี้ เราใช้ recursive approach เพื่อหาตัวเลขของเราแทนที่จะเป็น iterative

Complexity Analysis

Binary search algorithm มี best case complexity ของ O(1) นี่เกิดขึ้นเมื่อ item แรกที่ถูกเปรียบเทียบโดย algorithm เป็นตัวที่ถูกค้นหา

Binary search algorithm มี average และ worst case complexity ของ O(log n) นี่หมายความว่า ในส่วนใหญ่และใน worst case ความเร็วของ algorithm ช้าลงแบบ logarithmic ขึ้นอยู่กับจำนวน items ที่รายการต้อง search ผ่าน

สรุป

Binary searches ใช้หาตำแหน่งของ element ใน sorted list Binary searches เปรียบเทียบ item ในกลางของส่วนหนึ่งของ array กับตัวเลขที่ algorithm กำลังค้นหา

Binary searches มีประสิทธิภาพมากกว่า linear searches เพราะทุกครั้งที่ search ทำ จำนวน values ที่ต้อง search ผ่านถูกหารด้วยสอง

ตอนนี้คุณพร้อมที่จะ implement binary search ใน Java อย่างโปรแกรมเมอร์เชี่ยวชาญแล้ว