การค้นหาเชิงเส้นใน Java เป็นวิธีการค้นหาองค์ประกอบในอาร์เรย์มาโดยตลอด โดยจะค้นหาแต่ละองค์ประกอบของอาร์เรย์ตามลำดับและใช้งานได้ง่ายมาก อย่างไรก็ตาม ข้อบกพร่องของการค้นหาเชิงเส้นนั้นชัดเจนเมื่ออาร์เรย์ที่เป็นปัญหามีองค์ประกอบหลายหมื่นรายการ ในกรณีเช่นนี้ วิธี "แบ่งและพิชิต" ที่ใช้โดย Binary Search นั้นมีประสิทธิภาพมากกว่าและเป็นที่นิยมมากกว่าสำหรับโปรแกรมเมอร์ที่คำนึงถึงความซับซ้อนของเวลาและพื้นที่
การค้นหาไบนารี
ในการค้นหาแบบไบนารี อาร์เรย์จะถูกแบ่งออกเป็นสองซีกซ้ำๆ จนกว่าจะพบคีย์ (องค์ประกอบที่กำลังค้นหา) การแบ่งนั้นเสมือนคือการรักษาความสมบูรณ์ของข้อมูล ทุกครั้งที่วนซ้ำ ค่ากลางของอาร์เรย์จะถูกโฟกัส หากค่าเท่ากับคีย์ที่เราต้องการ ฟังก์ชันวนซ้ำหรือเรียกซ้ำจะสิ้นสุดลง มิฉะนั้นจะยังคงวนซ้ำ ถ้าค่ากลางมากกว่าคีย์ ฟังก์ชันจะเน้นที่ครึ่งแรกของอาร์เรย์และในทางกลับกัน กระบวนการนี้ซ้ำจนกว่าจะพบคีย์หรือวนซ้ำอาร์เรย์ทั้งหมด
ความแตกต่างระหว่างการค้นหาเชิงเส้นและไบนารี
การค้นหาเชิงเส้น |
การค้นหาไบนารี |
ค้นหาอาร์เรย์ตามลำดับ |
แบ่งอาร์เรย์ออกเป็นสองซีกจนกว่าจะพบค่า |
ทำงานร่วมกับอาร์เรย์ใดก็ได้ |
ใช้งานได้กับอาร์เรย์ที่เรียงลำดับเท่านั้น |
ความซับซ้อนคือ O(N) |
ความซับซ้อนคือ O(log2N) |
สามารถทำงานกับอาร์เรย์ที่เรียงลำดับและไม่เรียงลำดับได้ |
ใช้งานได้กับอาร์เรย์ที่เรียงลำดับเท่านั้น |
ซับซ้อนน้อยกว่าในการดำเนินการ |
ซับซ้อนมากขึ้นในการดำเนินการ |
อัลกอริทึมการค้นหาแบบไบนารี
อัลกอริทึมของ Binary Search แสดงไว้ด้านล่าง
- กำหนดจุดแรกและจุดสุดท้ายของอาร์เรย์ คะแนนจะถูกปรับในการวนซ้ำแต่ละครั้งตามอาร์เรย์และคีย์ที่กำลังค้นหา
- วนซ้ำในอาร์เรย์และเปรียบเทียบค่ากลางระหว่างจุดแรกและจุดสุดท้ายปัจจุบันของคุณ ในการวนซ้ำครั้งแรก ตัวแปรตัวแรกและตัวสุดท้ายจะเหมือนกับตัวแปรจริงในอาร์เรย์
- หากคีย์มีค่ามากกว่าค่ากลาง ดัชนีของค่านั้นจะถูกเก็บไว้ในตัวแปร "ตัวแรก" ใหม่
- หากคีย์มีค่าน้อยกว่าค่ากลาง ดัชนีของค่านั้นจะถูกเก็บไว้ในตัวแปร 'สุดท้าย'
- เงื่อนไขนี้จะเกิดซ้ำจนกว่าหนึ่งในสองเงื่อนไขจะเป็นจริง:
- พบกุญแจแล้ว
- อาร์เรย์ทั้งหมดได้รับการวนซ้ำ
รหัสสำหรับทั้งการค้นหาไบนารีแบบวนซ้ำและการค้นหาไบนารีแบบเรียกซ้ำมีดังต่อไปนี้
การค้นหาไบนารีซ้ำ
รหัสสำหรับการค้นหาแบบไบนารีด้วยวิธีการวนซ้ำมีดังต่อไปนี้
import java.util.Scanner;
public class IterativeBinarySearch {
public static void main(String[] args) {
int arr[] = {1,3,6,8,10};
System.out.println("Enter Number to Search For: ");
Scanner input = new Scanner (System.in);
int num = input.nextInt();
int result = BinarySearchIterative(arr,num);
if(result!=-1)
System.out.println("Value Found at Index #" + result);
else
System.out.println("Value Not Found");
}
public static int BinarySearchIterative(int[] arr, int num){
//Representing the Start and End Index After Division of Array
int start = 0;
int end = arr.length;
//Loop to Iterate Through the Array
for(int i = 0; iarr[n]){
start = n;
}
//If number to search for is greater than the arr value at index 'n'
else{
end = n;
}
}
//If number isn't found, return -1
return -1;
}
}
การค้นหาไบนารีแบบเรียกซ้ำ
รหัสสำหรับไบนารีโดยใช้การเรียกซ้ำจะได้รับด้านล่าง
import java.util.Scanner;
public class RecursiveBinarySearch {
public static void main(String[] args) {
int arr[] = {1,3,6,8,10};
System.out.println("Enter Number to Search For: ");
Scanner input = new Scanner (System.in);
int num = input.nextInt();
int result = BinarySearchRecursive(arr,0,arr.length-1,num);
if(result!=-1)
System.out.println("Value Found at Index #" + result);
else
System.out.println("Value Not Found");
}
public static int BinarySearchRecursive(int arr[], int a, int b, int num){
//Base Case to Exit the Recursive Function
if (b < 1) {
return -1;
}
int n = a + (b=1)/2;
//If number is found at mean index of start and end
if(arr[n]==num)
return n;
//If number to search for is greater than the arr value at index 'n'
else if(arr[n]>num)
return BinarySearchRecursive(arr,a,n-1,num);
//If number to search for is greater than the arr value at index 'n'
else
return BinarySearchRecursive(arr,n+1,b,num);
}
}
ความซับซ้อนของเวลา
ด้วยการวนซ้ำทุกครั้ง อาร์เรย์เช่นพื้นที่การค้นหาจะถูกแบ่งครึ่ง หลังจากการวนซ้ำ "m" ทุกครั้ง พื้นที่ค้นหาจะเปลี่ยนเป็นขนาด N/2m ในกรณีที่เลวร้ายที่สุด เราจะเหลือเพียงองค์ประกอบเดียวที่ด้านไกลของอาร์เรย์ ในขณะนี้ ความซับซ้อนของการค้นหาแบบไบนารีจะเป็น k = log2N ความซับซ้อนของเวลาของการค้นหาเชิงเส้นคือ O(N) ซึ่งส่งผลให้การค้นหาแบบไบนารีเร็วขึ้นมากด้วยความซับซ้อน O(log2N) นี่คือประโยชน์หลักของการใช้การค้นหาแบบไบนารีมากกว่าการค้นหาเชิงเส้น
ความซับซ้อนของอวกาศ
การค้นหาแบบไบนารีใช้ตัวแปรที่แตกต่างกันสามตัว — เริ่มต้น สิ้นสุด และกลาง ตัวแปรทั้งสามนี้ถูกสร้างขึ้นเป็นตัวชี้ซึ่งชี้ไปยังตำแหน่งหน่วยความจำของดัชนีอาร์เรย์ ด้วยเหตุนี้การค้นหาแบบไบนารีจึงมีประสิทธิภาพอย่างมากด้วยพื้นที่ว่าง ความซับซ้อนของช่องว่างของการค้นหาไบนารีแบบวนซ้ำคือ O(1) สำหรับการใช้งานแบบเรียกซ้ำ มันคือ O(log N)
GO TO FULL VERSION