• โฮมเพจ
  • บทความ
  • ทั่วไป
  • การค้นหาเชิงเส้นและการค้นหาแบบไบนารี: ความแตกต่างระหว่างการค้นหาเชิงเส้นและการค้นหาแบบไบนารี

การค้นหาเชิงเส้นและการค้นหาแบบไบนารี: ความแตกต่างระหว่างการค้นหาเชิงเส้นและการค้นหาแบบไบนารี

เผยแพร่แล้ว: 2021-02-09

สารบัญ

บทนำ

การจัดสรรหน่วยความจำที่ต่อเนื่องกันในภาษาโปรแกรมทำให้การใช้งานการจัดเก็บหลายจุดข้อมูลเป็นไปอย่างยืดหยุ่น สามารถใช้ที่จุดสูงสุดได้ หากเราต้องการแยกข้อมูลและรวมข้อมูลที่คล้ายกันทั้งหมดในโครงสร้างข้อมูลที่ต่อเนื่องกัน เช่น อาร์เรย์ รายการ ฯลฯ

การจัดสรรหน่วยความจำต่อเนื่องมีการใช้งานหลายอย่างในแอปพลิเคชันจริง เช่น ระบบปฏิบัติการในคอมพิวเตอร์ ระบบจัดการฐานข้อมูล เป็นต้น โครงสร้างข้อมูลนี้ถือเป็นโครงสร้างที่ยืดหยุ่นได้ เนื่องจากการเพิ่มจุดข้อมูลใหม่ลงในอาร์เรย์ต้องใช้เวลาเพียงหน่วยเดียว เช่น โอ(1).

แต่ปัญหาเกิดขึ้นเมื่อเราต้องการดูรายการใดรายการหนึ่งหรือค้นหารายการใดรายการหนึ่ง เนื่องจากแอพพลิเคชั่นในโลกแห่งความจริงทั้งหมดอาศัยคำสั่งในการเข้าถึงข้อมูล และงานนี้ต้องเร็วพอที่จะตอบสนองความเร็วของโปรเซสเซอร์และหน่วยความจำ

มีอัลกอริธึมการค้นหาที่หลากหลายซึ่งแบ่งตามจำนวนการเปรียบเทียบที่เราทำเพื่อค้นหาองค์ประกอบ

หากเราเปรียบเทียบจุดข้อมูลแต่ละจุดในอาร์เรย์เพื่อค้นหาองค์ประกอบ ก็จะถือว่าเป็นการค้นหาตามลำดับ แต่ถ้าเรากำลังเปรียบเทียบองค์ประกอบเพียงไม่กี่อย่างโดยข้ามการเปรียบเทียบบางรายการ ก็จะถือว่าเป็นการค้นหาตามช่วงเวลา แต่เราต้องการให้อาร์เรย์อยู่ในลำดับการจัดเรียง (จากน้อยไปมากหรือจากมากไปหาน้อย) เพื่อทำการค้นหาตามช่วงเวลา

ความซับซ้อนของเวลาของการค้นหาตามลำดับคือ O(n) เชิงเส้น และความซับซ้อนของเวลาของการค้นหาแบบไบนารี (ตัวอย่างของการค้นหาตามช่วงเวลา) คือ O(log n) นอกจากนี้ยังมีอัลกอริธึมการค้นหาอื่นๆ เช่น การค้นหาแบบเอ็กซ์โพเนนเชียล การค้นหาแบบข้าม ฯลฯ

แต่การค้นหาเชิงเส้นและการค้นหาแบบไบนารีส่วนใหญ่จะใช้ โดยการค้นหาเชิงเส้นใช้สำหรับข้อมูลแบบสุ่มหรือไม่เรียงลำดับ และการค้นหาแบบไบนารีใช้สำหรับข้อมูลที่เรียงลำดับและเรียงลำดับ การแฮชเป็นอัลกอริธึมการค้นหาพิเศษที่ความซับซ้อนของเวลาในการเข้าถึงจุดข้อมูลคือ O(1)

ขั้นแรก มาดูอัลกอริทึมของการค้นหาเชิงเส้นและการค้นหาแบบไบนารีก่อน จากนั้นจึงเปรียบเทียบความแตกต่างระหว่างการค้นหาเชิงเส้นและการค้นหาแบบไบนารี

ค้นหาเชิงเส้น

ตามที่กล่าวไปแล้ว อัลกอริธึมการค้นหาเชิงเส้นจะเปรียบเทียบแต่ละองค์ประกอบในอาร์เรย์ และนี่คือโค้ดที่ต้องทำ

ชั้นเรียนสาธารณะ UpGrad {
 int คงที่ สาธารณะ linear_search ( int [] arr, int n, int k){
 สำหรับ ( int i= 0 ; i<n; i++)
 ถ้า (arr[i]==k)
 ส่งคืน i+ 1 ;
 กลับ – 1 ;
 }
 โมฆะ คงที่ สาธารณะ หลัก (สตริง[] args){
 int [] arr= ใหม่ int []{ 1 , 2 , 5 , 6 , 3 , 8 , 9 , 9 , 0 , 13 , 45 , 65 };
 int k= 13 ;
 int n=arr.length;
 int r=linear_search(arr, n, k);
 ถ้า (r==- 1 )
 System.out.println( “ไม่พบองค์ประกอบ” );
 อื่น
 System.out.println( “พบองค์ประกอบที่ตำแหน่ง “ +r+ ” );
 }
 }

มาดูโค้ดกันเลย

เราได้ประกาศฟังก์ชัน linear_search ซึ่งคาดว่าอาร์เรย์ คีย์จำนวนเต็มเป็นพารามิเตอร์ ตอนนี้ เราต้องวนรอบองค์ประกอบทั้งหมดและเปรียบเทียบว่าตรงกับคีย์การค้นหาของเราหรือไม่ เราจึงเขียน for loop ที่วนรอบอาร์เรย์ และภายในมี if loop ที่ตรวจสอบว่าตัวเลขที่ตำแหน่งนั้นตรงกันหรือไม่ ด้วยปุ่มค้นหาหรือไม่ หากเราพบการแข่งขัน เราจะคืนตำแหน่ง หากไม่มีองค์ประกอบดังกล่าวในอาร์เรย์ เราจะคืนค่า -1 ที่ส่วนท้ายของฟังก์ชัน

โปรดทราบว่าหากเราปรากฏตัวเลขเดียวกันหลายครั้ง เราจะคืนตำแหน่งที่เกิดขึ้นครั้งแรก

มาถึงวิธีการหลัก เราได้ประกาศและเริ่มต้นอาร์เรย์จำนวนเต็ม จากนั้นเราจะเริ่มต้นคีย์ที่จะต้องค้นหา ที่นี่เรากำลังฮาร์ดโค้ดอาร์เรย์และคีย์ แต่คุณสามารถเปลี่ยนเป็นอินพุตของผู้ใช้ได้ ตอนนี้เราได้รายการองค์ประกอบและคีย์ที่จะค้นหาแล้ว วิธีการค้นหาเชิงเส้นจะถูกเรียกและดัชนีที่ส่งคืนจะถูกบันทึก ต่อมา เราจะตรวจสอบค่าที่ส่งคืนและพิมพ์ดัชนีหากมีคีย์ มิฉะนั้น ไม่พบคีย์การพิมพ์

ค้นหาไบนารี

การค้นหาแบบไบนารีได้รับการปรับให้เหมาะสมมากกว่าการค้นหาเชิงเส้น แต่ต้องจัดเรียงอาร์เรย์เพื่อใช้การค้นหาแบบไบนารี และนี่คือรหัสที่จะทำเช่นนั้น

ชั้นเรียน สาธารณะ UpGrad {
 ส แตติก int binary_search สาธารณะ ( int [] arr, int k){
 int l= 0 ,h=arr.length- 1 ,กลาง= 0 ;
 ในขณะที่ (ล.<=ชั่วโมง){
 กลาง=l+(hl)/ 2 ;
 ถ้า (arr[กลาง]==k)
 คืนค่า กลาง+ 1 ;
 อื่น ถ้า (arr[กลาง]>k)
 ชั่วโมง=กลาง- 1 ;
 อื่น
 ล.=กลาง+ 1 ;
 }
 กลับ – 1 ;
 }
 โมฆะ คงที่ สาธารณะ หลัก (สตริง[] args){
 int [] arr= ใหม่ int []{ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 };
 int k= 8 ;
 int r=binary_search(arr,k);
 ถ้า (r==- 1 )
 System.out.println( “ไม่พบองค์ประกอบ” );
 อื่น
 System.out.println( “พบองค์ประกอบที่ตำแหน่ง “ +r+ ” );
 }
 }

มาดูโค้ดกันเลย

เราได้ประกาศเมธอด binary_search ซึ่งคาดว่าจะมีการจัดเรียงอาร์เรย์จำนวนเต็มและคีย์จำนวนเต็มเป็นพารามิเตอร์ เรากำลังเริ่มต้นตัวแปร ต่ำ สูง กลาง ค่าต่ำสุด สูง คือตัวชี้ โดยที่ค่าต่ำสุดจะอยู่ที่ 0 ดัชนี และค่าสูงจะอยู่ที่ n ดัชนีในตอนเริ่มต้น การค้นหาแบบไบนารีทำงานอย่างไร

ขั้นแรก เราจะคำนวณค่ากลางของค่าต่ำสุดและค่าสูงสุด เราสามารถคำนวณค่ากลางเป็น (ต่ำ+สูง)/2 แต่บางครั้งสูงอาจเป็นตัวเลขที่มาก และการบวกค่าต่ำไปสูงอาจทำให้จำนวนเต็มล้น ดังนั้น การคำนวณ mid เป็น low+(high-low)/2 จะเป็นวิธีที่เหมาะสมที่สุด

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

ในทำนองเดียวกัน หาก mid มีค่าน้อยกว่าคีย์ เราต้องค้นหาในช่วงครึ่งหลังของอาร์เรย์ ดังนั้นจึงอัปเดตค่า low เป็น mid+1 อย่าลืมว่าการค้นหาแบบไบนารีนั้นขึ้นอยู่กับอัลกอริธึมการลดและพิชิต เนื่องจากเราละเลยครึ่งหนึ่งของอาร์เรย์ในการวนซ้ำแต่ละครั้ง

กลับมาที่โค้ดของเรา เราได้สร้างวิธีการหลัก เริ่มต้นอาร์เรย์ที่จัดเรียงและคีย์การค้นหา เรียกการค้นหาแบบไบนารี และพิมพ์ผลลัพธ์

ตอนนี้เราได้ศึกษาอัลกอริทึมของทั้งการค้นหาเชิงเส้นและการค้นหาแบบไบนารีแล้ว เรามาเปรียบเทียบอัลกอริทึมทั้งสองกัน

การค้นหาเชิงเส้นและการค้นหาแบบไบนารี

การทำงาน

  • การค้นหาเชิงเส้นจะวนซ้ำองค์ประกอบทั้งหมดและเปรียบเทียบกับคีย์ที่ต้องค้นหา
  • การค้นหาแบบไบนารีจะลดขนาดของอาร์เรย์ที่ต้องค้นหาอย่างชาญฉลาด และเปรียบเทียบคีย์กับองค์ประกอบกลางทุกครั้ง

โครงสร้างข้อมูล

  • การค้นหาเชิงเส้นมีความยืดหยุ่นกับโครงสร้างข้อมูลทั้งหมด เช่น อาร์เรย์ รายการ รายการที่เชื่อมโยง ฯลฯ
  • ไม่สามารถดำเนินการค้นหาแบบไบนารีในโครงสร้างข้อมูลทั้งหมดได้ เนื่องจากเราต้องการการข้ามผ่านหลายทิศทาง ดังนั้นโครงสร้างข้อมูลเช่นรายการที่เชื่อมโยงเดียวจึงไม่สามารถใช้ได้

ข้อกำหนดเบื้องต้น

  • การค้นหาเชิงเส้นสามารถทำได้กับข้อมูลทุกประเภท ข้อมูลสามารถสุ่มหรือจัดเรียงอัลกอริทึมได้เหมือนเดิม ดังนั้นจึงไม่จำเป็นต้องเตรียมงานล่วงหน้าใดๆ
  • การค้นหาแบบไบนารีใช้งานได้กับอาร์เรย์ที่เรียงลำดับเท่านั้น ดังนั้นการเรียงลำดับอาร์เรย์จึงเป็นข้อกำหนดเบื้องต้นสำหรับอัลกอริทึมนี้

ใช้กรณี

  • โดยทั่วไปควรใช้การค้นหาเชิงเส้นสำหรับชุดข้อมูลที่มีขนาดเล็กกว่าและมีการเรียงลำดับแบบสุ่ม
  • ควรใช้การค้นหาแบบไบนารีสำหรับชุดข้อมูลที่มีขนาดใหญ่กว่าและเรียงลำดับแล้ว

ประสิทธิผล

  • การค้นหาเชิงเส้นมีประสิทธิภาพน้อยกว่าในกรณีของชุดข้อมูลขนาดใหญ่
  • การค้นหาแบบไบนารีมีประสิทธิภาพมากกว่าในกรณีของชุดข้อมูลขนาดใหญ่

ความซับซ้อนของเวลา

  • ในการค้นหาเชิงเส้น ความซับซ้อนของกรณีที่ดีที่สุดคือ O(1) โดยที่องค์ประกอบจะอยู่ที่ดัชนีแรก ความซับซ้อนของกรณีที่เลวร้ายที่สุดคือ O(n) ซึ่งพบองค์ประกอบที่ดัชนีสุดท้ายหรือองค์ประกอบไม่มีอยู่ในอาร์เรย์
  • ในการค้นหาแบบไบนารี ความซับซ้อนของตัวพิมพ์เล็กที่ดีที่สุดคือ O(1) โดยที่องค์ประกอบจะอยู่ที่ดัชนีตรงกลาง ความซับซ้อนของกรณีที่เลวร้ายที่สุดคือ O( log 2 n)

วิ่งแห้ง

สมมติว่าเรามีอาร์เรย์ขนาด 10,000

  • ในการค้นหาเชิงเส้น ความซับซ้อนของกรณีที่ดีที่สุดคือ O(1) และความซับซ้อนของกรณีที่เลวร้ายที่สุดคือ O(10000)
  • ในการค้นหาแบบไบนารี ความซับซ้อนของเคสที่ดีที่สุดคือ O(1) และความซับซ้อนของเคสที่แย่ที่สุดคือ O( log 2 10000)=O(13.287)

บทสรุป

เราเข้าใจถึงความสำคัญของการเข้าถึงข้อมูลในอาร์เรย์ เข้าใจอัลกอริทึมของการค้นหาเชิงเส้นและการค้นหาแบบไบนารี เดินผ่านรหัสของการค้นหาเชิงเส้นและการค้นหาแบบไบนารี เมื่อเปรียบเทียบความแตกต่างระหว่างการค้นหาเชิงเส้นและการค้นหาแบบไบนารี ได้ดำเนินการแบบแห้งสำหรับตัวอย่างขนาดใหญ่

ตอนนี้ คุณทราบถึงความแตกต่างระหว่างการค้นหาเชิงเส้นและการค้นหาแบบไบนารีแล้ว ให้ลองเรียกใช้โค้ดทั้งสองสำหรับชุดข้อมูล sied ขนาดใหญ่และเปรียบเทียบเวลาดำเนินการ เริ่มสำรวจอัลกอริธึมการค้นหาต่างๆ และลองใช้มัน!

หากคุณอยากเรียนรู้เกี่ยวกับวิทยาศาสตร์ข้อมูล ให้ลองดูประกาศนียบัตร PG ด้านวิทยาศาสตร์ข้อมูลของ IIIT-B และ upGrad ซึ่งสร้างขึ้นสำหรับมืออาชีพด้านการทำงานและเสนอกรณีศึกษาและโครงการมากกว่า 10 รายการ เวิร์กช็อปภาคปฏิบัติจริง การให้คำปรึกษากับผู้เชี่ยวชาญในอุตสาหกรรม 1- on-1 กับที่ปรึกษาในอุตสาหกรรม การเรียนรู้มากกว่า 400 ชั่วโมงและความช่วยเหลือด้านงานกับบริษัทชั้นนำ

เรียนรู้ หลักสูตรวิทยาศาสตร์ข้อมูล ออนไลน์จากมหาวิทยาลัยชั้นนำของโลก รับโปรแกรม PG สำหรับผู้บริหาร โปรแกรมประกาศนียบัตรขั้นสูง หรือโปรแกรมปริญญาโท เพื่อติดตามอาชีพของคุณอย่างรวดเร็ว

เปรียบเทียบการค้นหาเชิงเส้นและการค้นหาแบบไบนารีโดยใช้ความซับซ้อน

การค้นหาแบบไบนารีได้รับการปรับให้เหมาะสมและมีประสิทธิภาพมากกว่าการค้นหาเชิงเส้นในหลาย ๆ ด้าน โดยเฉพาะอย่างยิ่งเมื่อองค์ประกอบอยู่ในลำดับการจัดเรียง สาเหตุมาจากความซับซ้อนของการค้นหาทั้งสองแบบ
ค้นหาเชิงเส้น
1. ความซับซ้อนของเวลา: O(N) - เนื่องจากในการค้นหาเชิงเส้น เราสำรวจผ่านอาร์เรย์เพื่อตรวจสอบว่าองค์ประกอบใดตรงกับคีย์หรือไม่ ในสถานการณ์ที่แย่ที่สุด องค์ประกอบจะปรากฏที่ส่วนท้ายของอาร์เรย์ ดังนั้นเราต้องข้ามผ่านจุดสิ้นสุด และด้วยเหตุนี้ความซับซ้อนของเวลาจะเป็น O(N) โดยที่ N คือจำนวนองค์ประกอบอาร์เรย์ทั้งหมด
2. Space Complexity: O(1) - เราไม่ได้ใช้ช่องว่างพิเศษใดๆ ดังนั้นความซับซ้อนของพื้นที่จะเป็น O(1)
ค้นหาไบนารี
1. ความซับซ้อนของเวลา: O(log N) - ใน Binary Search การค้นหาจะลดลงเหลือครึ่งหนึ่ง เนื่องจากเราต้องมองขึ้นไปตรงกลางอาร์เรย์เท่านั้น และเรากำลังย่อการค้นหาของเราให้สั้นลงอย่างต่อเนื่องจนถึงกลางส่วนที่มีองค์ประกอบอยู่
2. ความซับซ้อนของอวกาศ: O(1)
- เราไม่ได้ใช้พื้นที่พิเศษใด ๆ ดังนั้นความซับซ้อนของพื้นที่จะเป็น O(1)

มีวิธีอื่นในการค้นหาองค์ประกอบในอาร์เรย์หรือไม่?

แม้ว่าการค้นหาเชิงเส้นและการค้นหาแบบไบนารีมักจะใช้สำหรับการค้นหา แต่ก็มีวิธีค้นหาอีกวิธีหนึ่ง นั่นคือ วิธีการแก้ไข เป็นเวอร์ชันที่ปรับให้เหมาะสมของ Binary Search โดยที่องค์ประกอบทั้งหมดจะถูกกระจายอย่างเท่าเทียมกัน
แนวคิดเบื้องหลังวิธีนี้คือในการค้นหาแบบไบนารี เรามักจะมองขึ้นไปที่กึ่งกลางของอาร์เรย์ แต่ในวิธีนี้ การค้นหาสามารถไปยังตำแหน่งต่างๆ ได้ขึ้นอยู่กับตำแหน่งของคีย์ ตัวอย่างเช่น หากคีย์อยู่ใกล้กับองค์ประกอบสุดท้ายของอาร์เรย์ การค้นหาจะเริ่มจากส่วนท้ายของอาร์เรย์

อะไรคือความซับซ้อนของเวลาที่แตกต่างกันของการค้นหาการแก้ไข?

ความซับซ้อนของเวลาในกรณีที่เลวร้ายที่สุดของการค้นหาการแก้ไขคือ O(N) เนื่องจากในกรณีที่เลวร้ายที่สุด คีย์จะอยู่ที่ส่วนท้ายของอาร์เรย์ ดังนั้นตัววนซ้ำจึงต้องสำรวจทั่วทั้งอาร์เรย์
ความซับซ้อนของตัวพิมพ์เฉลี่ยจะเป็น O(log(log N) เนื่องจากองค์ประกอบสามารถอยู่ที่ใดก็ได้ในอาร์เรย์ อาจอยู่ใกล้จุดเริ่มต้นด้วย
ความซับซ้อนของกรณีที่ดีที่สุดจะเป็น O(1) เนื่องจากในกรณีที่ดีที่สุด คีย์จะเป็นองค์ประกอบแรกสุดของอาร์เรย์