วิธีใช้ Binary Search Algorithm ใน Java โดยไม่ต้องเรียกซ้ำ

การใช้อัลกอริธึมการค้นหาไบนารีที่เป็นที่นิยมซ้ำ ๆ เพื่อค้นหาองค์ประกอบในอาร์เรย์ที่เรียงลำดับ

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

ใช่คุณเดาถูก: คุณต้องใช้การค้นหาแบบไบนารีใน Java และคุณต้องเขียนอัลกอริทึมการค้นหาไบนารีแบบวนซ้ำและวนซ้ำ

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

การเปรียบเทียบจะพิจารณาว่าองค์ประกอบเท่ากับอินพุตน้อยกว่าอินพุตหรือมากกว่าอินพุต

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

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

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

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

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

Btw หากคุณไม่คุ้นเคยกับการค้นหาพื้นฐานและอัลกอริทึมการจัดเรียงคุณสามารถเข้าร่วมหลักสูตรเช่นโครงสร้างข้อมูลและอัลกอริทึม: การดำน้ำลึกโดยใช้ Javaเพื่อเรียนรู้อัลกอริทึมพื้นฐาน

หาก Java ไม่ใช่ภาษาที่คุณเลือกคุณสามารถดูคำแนะนำเพิ่มเติมสำหรับ JavaScript และ Python ได้ในรายการหลักสูตรอัลกอริทึมนี้

Btw ถ้าคุณชอบหนังสือฉันขอแนะนำให้คุณอ่านหนังสืออัลกอริทึมที่ครอบคลุมเช่นIntroduction to Algorithmsโดย Thomas H. Cormen

นี่คือโค้ดตัวอย่างบางส่วนที่แสดงตรรกะของการค้นหาไบนารีแบบวนซ้ำใน Java :

การใช้งานการค้นหาแบบไบนารีใน Java

นี่คือโปรแกรมตัวอย่างเพื่อใช้การค้นหาไบนารีใน Java อัลกอริทึมถูกนำมาใช้ซ้ำ นอกจากนี้ข้อเท็จจริงที่น่าสนใจที่ควรทราบเกี่ยวกับการใช้งานการค้นหาไบนารีใน Java ก็คือ Joshua Bloch ผู้เขียนหนังสือ Effective Java ที่มีชื่อเสียงเขียนการค้นหาไบนารีใน "java.util.Arrays"

import java.util.Arrays;import java.util.Scanner;
/** * Java program to implement Binary Search. We have implemented Iterative* version of Binary Search Algorithm in Java** @author Javin Paul*/
public class IterativeBinarySearch {
 public static void main(String args[]) { int[] list = new int[]{23, 43, 31, 12}; int number = 12; Arrays.sort(list); System.out.printf("Binary Search %d in integer array %s %n", number, Arrays.toString(list));
 binarySearch(list, 12); System.out.printf("Binary Search %d in integer array %s %n", 43, Arrays.toString(list));
 binarySearch(list, 43); list = new int[]{123, 243, 331, 1298}; number = 331; Arrays.sort(list); System.out.printf("Binary Search %d in integer array %s %n", number, Arrays.toString(list));
 binarySearch(list, 331); System.out.printf("Binary Search %d in integer array %s %n", 331, Arrays.toString(list)); binarySearch(list, 1333);
 // Using Core Java API and Collection framework // Precondition to the Arrays.binarySearch Arrays.sort(list);
 // Search an element int index = Arrays.binarySearch(list, 3);
}
/** * Perform a binary Search in Sorted Array in Java * @param input * @param number * @return location of element in array */
public static void binarySearch(int[] input, int number) {int first = 0;int last = input.length - 1;int middle = (first + last) / 2;
while (first <= last) { if (input[middle] < number) { first = middle + 1;} else if (input[middle] == number) {
System.out.printf(number + " found at location %d %n", middle);break;} else { last = middle - 1;}
middle = (first + last) / 2;
}
if (first > last) { System.out.println(number + " is not present in the list.\n");}
}
}
OutputBinary Search 12 in integer array [12, 23, 31, 43]12 found at location 0Binary Search 43 in integer array [12, 23, 31, 43]43 found at location 3Binary Search 331 in integer array [123, 243, 331, 1298]331 found at location 2Binary Search 331 in integer array [123, 243, 331, 1298]1333 is not present in the list.

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

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

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

การเรียนรู้เพิ่มเติม

โครงสร้างข้อมูลและอัลกอริทึม: เจาะลึกโดยใช้ Java

อัลกอริทึมและโครงสร้างข้อมูล - ส่วนที่ 1 และ 2

โครงสร้างข้อมูลใน Java 9 โดย Heinz Kabutz

หนังสืออัลกอริทึม 10 เล่มสำหรับการสัมภาษณ์

10 โครงสร้างข้อมูลและอัลกอริทึมสำหรับการสัมภาษณ์

5 หลักสูตรฟรีเพื่อเรียนรู้โครงสร้างข้อมูลและอัลกอริทึม

แบบฝึกหัดโครงสร้างข้อมูลและอัลกอริทึมอื่น ๆ ที่คุณอาจชอบ

  • วิธีการใช้ Quicksort algorithm ใน Java? (กวดวิชา)
  • จะใช้ Binary Search Tree ใน Java ได้อย่างไร? (วิธีการแก้)
  • จะใช้อัลกอริทึม Quicksort โดยไม่ต้องเรียกซ้ำได้อย่างไร? (กวดวิชา)
  • จะใช้อัลกอริทึมการเรียงลำดับการแทรกใน Java ได้อย่างไร? (กวดวิชา)
  • How to implement Bubble sort algorithm in Java? (tutorial)
  • What is the difference between Comparison and Non-Comparison based sorting algorithm? (answer)
  • How to implement Bucket Sort in Java? (tutorial)
  • How to implement a Binary Search Algorithm without recursion in Java? (tutorial)
  • 50+ Data Structure and Algorithms Courses for Programmers (questions)

Thanks for reading this article. If you like this article then please share with your friends and colleagues. If you have any suggestion or feedback then please drop a comment.

P.S. — If you are serious about improving your Algorithms skills, I think the Data Structures and Algorithms: Deep Dive Using Java is the best one to start with.