บทช่วยสอนนี้จะอธิบายการค้นหาแบบไบนารี & การค้นหาไบนารีแบบเรียกซ้ำใน Java พร้อมกับอัลกอริทึม การนำไปใช้งาน และตัวอย่างรหัสการค้นหาไบนารีของ Java:
การค้นหาแบบไบนารีใน Java เป็นเทคนิคที่ใช้เพื่อค้นหาค่าหรือคีย์เป้าหมายในคอลเลกชัน เป็นเทคนิคที่ใช้เทคนิค "แบ่งและพิชิต" เพื่อค้นหาคีย์
คอลเลกชันที่จะใช้การค้นหาแบบไบนารีเพื่อค้นหาคีย์จำเป็นต้องเรียงลำดับจากน้อยไปหามาก
โดยปกติแล้ว ภาษาโปรแกรมส่วนใหญ่สนับสนุนการค้นหาเชิงเส้น การค้นหาแบบไบนารี และเทคนิคการแฮชที่ใช้เพื่อค้นหาข้อมูลในคอลเลกชัน เราจะเรียนรู้การแฮชในบทเรียนถัดไปของเรา
การค้นหาแบบไบนารีใน Java
การค้นหาเชิงเส้นเป็นเทคนิคพื้นฐาน ในเทคนิคนี้ อาร์เรย์จะเคลื่อนที่ไปตามลำดับและแต่ละองค์ประกอบจะถูกเปรียบเทียบกับคีย์จนกว่าจะพบคีย์หรือถึงจุดสิ้นสุดของอาร์เรย์
การค้นหาเชิงเส้นไม่ค่อยถูกนำมาใช้ในแอปพลิเคชันที่ใช้งานจริง การค้นหาแบบไบนารีเป็นเทคนิคที่ใช้บ่อยที่สุด เนื่องจากเร็วกว่าการค้นหาแบบเชิงเส้นมาก
Java มีสามวิธีในการดำเนินการค้นหาแบบไบนารี:
- การใช้ วิธีการวนซ้ำ
- ใช้วิธีการเรียกซ้ำ
- การใช้เมธอด Arrays.binarySearch ()
ในบทช่วยสอนนี้ เราจะนำไปใช้และหารือเกี่ยวกับสิ่งเหล่านี้ทั้งหมด 3 วิธี
อัลกอริทึมสำหรับการค้นหาไบนารีใน Java
ในไบนารีวิธีการค้นหา คอลเลกชันจะถูกแบ่งออกเป็นครึ่งหนึ่งซ้ำๆ และองค์ประกอบหลักจะถูกค้นหาในครึ่งซ้ายหรือขวาของคอลเลกชัน ขึ้นอยู่กับว่าคีย์น้อยกว่าหรือมากกว่าองค์ประกอบตรงกลางของคอลเลกชัน
อัลกอริทึมการค้นหาแบบไบนารีอย่างง่ายมีดังนี้:
- คำนวณองค์ประกอบตรงกลางของคอลเลกชัน
- เปรียบเทียบรายการหลักกับองค์ประกอบตรงกลาง
- ถ้าคีย์ = องค์ประกอบตรงกลาง เราจะส่งคืนตำแหน่งดัชนีตรงกลางสำหรับคีย์ที่พบ
- Else ถ้าคีย์ > องค์ประกอบตรงกลาง จากนั้นคีย์จะอยู่ที่ครึ่งขวาของคอลเลกชัน ดังนั้นทำซ้ำขั้นตอนที่ 1 ถึง 3 ที่ด้านล่าง (ขวา) ของคอลเลกชัน
- ปุ่มอื่น องค์ประกอบตรงกลาง จากนั้นคีย์จะอยู่ที่ครึ่งบนของคอลเลกชัน ดังนั้น คุณต้องทำการค้นหาแบบไบนารีซ้ำในครึ่งบน
ดังที่คุณเห็นจากขั้นตอนข้างต้น ในการค้นหาแบบไบนารี องค์ประกอบครึ่งหนึ่งในคอลเลกชันจะถูกละเว้นหลังจากการเปรียบเทียบครั้งแรก
โปรดทราบว่าลำดับขั้นตอนเดียวกันถือเป็นการวนซ้ำและการค้นหาไบนารีแบบเรียกซ้ำ
ลองแสดงอัลกอริทึมการค้นหาแบบไบนารีโดยใช้ตัวอย่าง
ตัวอย่างเช่น นำอาร์เรย์ที่เรียงลำดับจาก 10 องค์ประกอบต่อไปนี้
มาคำนวณตำแหน่งตรงกลางของอาร์เรย์กัน
Mid = 0+9/2 = 4
#1) คีย์ = 21
ก่อนอื่น เราจะเปรียบเทียบค่าคีย์กับ [กลาง] และเราพบว่าองค์ประกอบมีค่าที่กลาง = 21
ดังนั้นเราจึงพบว่าคีย์ = [กลาง] ดังนั้นคีย์จึงอยู่ที่ตำแหน่ง 4 ในอาร์เรย์
#2) คีย์ = 25
ก่อนอื่นเราจะเปรียบเทียบคีย์ มูลค่าถึงกลาง เช่น (21 25) เราจะค้นหาคีย์โดยตรงในครึ่งบนของอาร์เรย์
ตอนนี้เราจะหาค่ากลางสำหรับครึ่งบนของ อาร์เรย์
กลาง = 4+9/2 = 6
ค่าที่ตำแหน่ง [กลาง] = 25
ตอนนี้ เปรียบเทียบองค์ประกอบหลักกับองค์ประกอบกลาง ดังนั้น (25 == 25) ดังนั้นเราจึงพบคีย์ที่ตำแหน่ง [กลาง] = 6
ดังนั้นเราจึงแบ่งอาร์เรย์ซ้ำๆ และโดยการเปรียบเทียบองค์ประกอบหลักกับตรงกลาง เราตัดสินใจว่าครึ่งไหนเป็น ค้นหากุญแจ การค้นหาแบบไบนารีมีประสิทธิภาพมากกว่าในแง่ของเวลาและความถูกต้อง และยังเร็วกว่ามากอีกด้วย
การใช้งานการค้นหาแบบไบนารี Java
การใช้อัลกอริทึมข้างต้น ให้เราติดตั้งโปรแกรมการค้นหาแบบไบนารีใน Java โดยใช้ วิธีการวนซ้ำ ในโปรแกรมนี้ เราจะใช้อาร์เรย์ตัวอย่างและทำการค้นหาแบบไบนารีในอาร์เรย์นี้
import java.util.*; class Main{ public static void main(String args[]){ int numArray[] = {5,10,15,20,25,30,35}; System.out.println("The input array: " + Arrays.toString(numArray)); //key to be searched int key = 20; System.out.println("\nKey to be searched=" + key); //set first to first index int first = 0; //set last to last elements in array int last=numArray.length-1; //calculate mid of the array int mid = (first + last)/2; //while first and last do not overlap while( first = last ){ //if the mid key, then key to be searched is in the first half of array if ( numArray[mid] last ){ System.out.println("Element is not found!"); } } }
เอาต์พุต:
อาร์เรย์อินพุต: [5, 10, 15, 20 , 25, 30, 35]
คีย์ที่จะค้นหา=20
พบองค์ประกอบที่ดัชนี: 3
โปรแกรมด้านบน แสดงวิธีการวนซ้ำของการค้นหาแบบไบนารี ในขั้นต้น อาร์เรย์จะถูกประกาศ จากนั้นจึงกำหนดคีย์ที่จะค้นหา
หลังจากคำนวณค่ากลางของอาร์เรย์แล้ว คีย์จะถูกเปรียบเทียบกับองค์ประกอบตรงกลาง แล้วแต่ว่าคีย์มีค่าน้อยกว่าหรือมากกว่าคีย์ คีย์จะถูกค้นหาในครึ่งล่างหรือครึ่งบนของอาร์เรย์ตามลำดับ
การค้นหาไบนารีแบบเรียกซ้ำใน Java
คุณยังสามารถทำการค้นหาไบนารี โดยใช้เทคนิคการเรียกซ้ำ ที่นี่ วิธีการค้นหาแบบไบนารีเรียกว่าเรียกซ้ำจนกว่าจะพบคีย์หรือรายการทั้งหมดหมด
โปรแกรมที่ใช้การค้นหาไบนารีแบบเรียกซ้ำมีดังต่อไปนี้:
import java.util.*; class Main{ //recursive method for binary search public static int binary_Search(int intArray[], int low, int high, int key){ //if array is in order then perform binary search on the array if (high>=low){ //calculate mid int mid = low + (high - low)/2; //if key =intArray[mid] return mid if (intArray[mid] == key){ return mid; } //if intArray[mid] > key then key is in left half of array if (intArray[mid] > key){ return binary_Search(intArray, low, mid-1, key);//recursively search for key }else //key is in right half of the array { return binary_Search(intArray, mid+1, high, key);//recursively search for key } } return -1; } public static void main(String args[]){ //define array and key int intArray[] = {1,11,21,31,41,51,61,71,81,91}; System.out.println("Input List: " + Arrays.toString(intArray)); int key = 31; System.out.println("\nThe key to be searched:" + key); int high=intArray.length-1; //call binary search method int result = binary_Search(intArray,0,high,key); //print the result if (result == -1) System.out.println("\nKey not found in given list!"); else System.out.println("\nKey is found at location: "+result + " in the list"); } }
เอาต์พุต:
รายการอินพุต: [1, 11, 21, 31, 41, 51, 61, 71, 81, 91
คีย์ที่จะค้นหา :
พบคีย์ที่ตำแหน่ง: 3 ในรายการ
โดยใช้วิธี Arrays.binarySearch ()
คลาสอาร์เรย์ใน Java มีเมธอด 'binarySearch ()' ที่ทำการค้นหาไบนารีในอาร์เรย์ที่กำหนด วิธีนี้ใช้อาร์เรย์และคีย์ที่จะค้นหาเป็นอาร์กิวเมนต์และส่งกลับตำแหน่งของคีย์ในอาร์เรย์ หากไม่พบคีย์ เมธอดจะส่งคืน -1
ตัวอย่างด้านล่างใช้เมธอด Arrays.binarySearch ()
import java.util.Arrays; class Main{ public static void main(String args[]){ //define an array int intArray[] = {10,20,30,40,50,60,70,80,90}; System.out.println("The input Array : " + Arrays.toString(intArray)); //define the key to be searched int key = 50; System.out.println("\nThe key to be searched:" + key); //call binarySearch method on the given array with key to be searched int result = Arrays.binarySearch(intArray,key); //print the return result if (result 0) System.out.println("\nKey is not found in the array!"); else System.out.println("\nKey is found at index: "+result + " in the array."); } }
เอาต์พุต:
อาร์เรย์อินพุต : [10, 20, 30, 40, 50, 60, 70, 80, 90]
คีย์ที่จะค้นหา:50
พบคีย์ที่ดัชนี: 4 ในอาร์เรย์
คำถามที่พบบ่อย
Q #1) คุณจะเขียนการค้นหาแบบไบนารีได้อย่างไร ?
คำตอบ: โดยปกติแล้วการค้นหาแบบไบนารีจะดำเนินการโดยการแบ่งอาร์เรย์ออกเป็นครึ่งๆ หากคีย์ที่ต้องการค้นหามากกว่าองค์ประกอบตรงกลางจากนั้นครึ่งบนของอาร์เรย์จะถูกค้นหาโดยการหารเพิ่มเติมและค้นหาอาร์เรย์ย่อยจนกว่าจะพบคีย์
ในทำนองเดียวกัน หากคีย์มีค่าน้อยกว่าองค์ประกอบตรงกลาง คีย์จะถูกค้นหาในส่วนล่าง ครึ่งหนึ่งของอาร์เรย์
Q #2) การค้นหาแบบไบนารีใช้ที่ไหน
คำตอบ: การค้นหาแบบไบนารีส่วนใหญ่ใช้เพื่อค้นหา ข้อมูลที่จัดเรียงในแอปพลิเคชันซอฟต์แวร์โดยเฉพาะอย่างยิ่งเมื่อพื้นที่หน่วยความจำมีขนาดกะทัดรัดและจำกัด
คำถาม #3) O ใหญ่ของการค้นหาแบบไบนารีคืออะไร
คำตอบ : ความซับซ้อนของเวลาของการค้นหาแบบไบนารีคือ O (logn) โดยที่ n คือจำนวนองค์ประกอบในอาร์เรย์ ความซับซ้อนของช่องว่างของการค้นหาแบบไบนารีคือ O (1)
Q #4) การค้นหาแบบไบนารีเป็นแบบเรียกซ้ำหรือไม่
คำตอบ: ใช่ เนื่องจากการค้นหาแบบไบนารีเป็นตัวอย่างของกลยุทธ์การแบ่งแยกและพิชิต และสามารถนำไปใช้ได้โดยใช้การเรียกซ้ำ เราสามารถแบ่งอาร์เรย์ออกเป็นครึ่งๆ และเรียกใช้เมธอดเดิมเพื่อทำการค้นหาแบบไบนารีซ้ำแล้วซ้ำอีก
Q #5) ทำไมถึงเรียกว่าการค้นหาแบบไบนารี
0 คำตอบ:อัลกอริทึมการค้นหาแบบไบนารีใช้กลยุทธ์การหารและพิชิตที่จะตัดอาร์เรย์ออกเป็นครึ่งหรือสองส่วนซ้ำๆ ดังนั้นจึงมีชื่อว่าการค้นหาแบบไบนารีสรุป
การค้นหาแบบไบนารีเป็นเทคนิคการค้นหาที่ใช้บ่อยใน Java ข้อกำหนดสำหรับการค้นหาแบบไบนารีที่จะดำเนินการคือ ข้อมูลควรเรียงลำดับจากน้อยไปหามาก
การค้นหาแบบไบนารีสามารถดำเนินการโดยใช้วิธีการวนซ้ำหรือเรียกซ้ำ คลาสอาร์เรย์ใน Java ยังมีเมธอด 'binarySearch' ที่ทำการค้นหาแบบไบนารีบนอาร์เรย์
ในบทช่วยสอนถัดไป เราจะสำรวจเทคนิคการเรียงลำดับต่างๆ ใน Java