Các thuật toán Tìm kiếm và Sắp xếp là thuật toán phổ biến bằng bất kỳ ngôn ngữ lập trình nào. Chúng là cơ sở để hiểu các nguyên tắc cơ bản của lập trình. Một thuật toán tìm kiếm phổ biến như vậy là Tìm kiếm nhị phân trong . Trong bài viết này, tôi sẽ cho bạn biết tất cả về cách thực hiện của nó.
Các chủ đề dưới đây được đề cập trong bài viết này:
Bắt đầu nào!
Tìm kiếm nhị phân là gì?
Tìm kiếm nhị phân trong là một thuật toán tìm kiếm tìm vị trí của giá trị đích trong một mảng . Tìm kiếm nhị phân so sánh giá trị đích với phần tử giữa của mảng. Nóchỉ hoạt động trên một tập hợp các phần tử đã được sắp xếp. Để sử dụng tìm kiếm nhị phân trên một bộ sưu tập, trước tiên phải được sắp xếp.
Khi mà được sử dụng để thực hiện các phép toán trên một tập hợp đã sắp xếp, số lần lặp luôn có thể được giảm bớt trên cơ sở giá trị đang được tìm kiếm. Bạn có thể thấy trong ảnh chụp nhanh ở trên về việc tìm kiếm yếu tố giữa . Tương tự của tìm kiếm nhị phân là sử dụng thông tin mà mảng được sắp xếp và giảm độ phức tạp về thời gian xuống O (log n) .
Triển khai thuật toán tìm kiếm nhị phân
Hãy xem mã giả bên dưới để hiểu nó theo cách tốt hơn.
Thủ tục binary_search A & larr đã sắp xếp mảng n & cỡ lớn của mảng x & giá trị larr cần tìm kiếm Đặt thấp = 1 Đặt cao = n trong khi không tìm thấy x nếu caoGiải trình:
Bước 1: Đầu tiên, so sánh x với phần tử ở giữa.
Bước 2: Nếu x khớp với phần tử ở giữa, thì bạn phải trả về chỉ số giữa.
Bước 3: Ngược lại, Nếu x lớn hơn phần tử giữa, thì x chỉ có thể nằm trong nửa mảng bên phải sau phần tử giữa. Do đó bạn tái diễn nửa bên phải.
Bước 4: Ngược lại, nếu (x nhỏ hơn) thì lặp lại cho nửa bên trái.
Đó là cách bạn cần tìm kiếm phần tử trong mảng đã cho.
ví dụ về webdriver java selenium dưa chuộtBây giờ chúng ta hãy xem cách triển khai thuật toán tìm kiếm nhị phân một cách đệ quy. Chương trình dưới đây trình bày tương tự.
Tìm kiếm nhị phân đệ quy
public class BinarySearch {// Triển khai Java tìm kiếm nhị phân đệ quy // Trả về chỉ mục của x nếu nó có trong arr [l..h], else trả về -1 int binarySearch (int a [], int l, int h, int x) {if (h> = l) {int mid = l + (h - l) / 2 // Nếu phần tử có ở chính giữa if (a [mid] == x) return mid // Nếu phần tử nhỏ hơn mid, thì nó chỉ có thể hiện diện trong mảng con bên trái nếu (a [mid]> x) return binarySearch (arr, l, mid - 1, x) // Khác phần tử chỉ có thể có trong mảng con bên phải trả về binarySearch (arr, mid + 1, h, x)} // Chúng ta đến đây khi phần tử không có trong mảng trả về -1} public static void main (String args []) {BinarySearch ob = new BinarySearch () int a [] = {20, 30, 40, 10, 50} int n = a.length int x = 40 int res = ob.binarySearch (a, 0, n - 1, x) if (res == -1) System.out .println ('Phần tử không có mặt') else System.out.println ('Phần tử được tìm thấy tại chỉ mục' + res)}}Khi thực hiện chương trình trên, nó sẽ xác định vị trí phần tử có trong chỉ mục cụ thể
Phần tử được tìm thấy ở chỉ mục 2Vì vậy, điều này đưa chúng ta đến phần cuối của Tìm kiếm nhị phân trong Java bài báo. Tôi hy vọng bạn tìm thấy nó thông tin và giúp bạn hiểu .
Kiểm tra của Edureka, một công ty học trực tuyến đáng tin cậy với mạng lưới hơn 250.000 người học hài lòng trải dài trên toàn cầu. Chúng tôi ở đây để giúp bạn từng bước trong hành trình của bạn, để trở thành người bên cạnh câu hỏi phỏng vấn java này. Chúng tôi đưa ra một chương trình giảng dạy được thiết kế cho sinh viên và các chuyên gia muốn trở thành một Nhà phát triển Java. Khóa học được thiết kế để cung cấp cho bạn khởi đầu về lập trình Java và đào tạo bạn về cả khái niệm Java cốt lõi và nâng cao cùng với các khung Java khác nhau như Hibernate & Spring.
Trong trường hợp bạn gặp bất kỳ khó khăn nào khi triển khai Tìm kiếm nhị phân trong , vui lòng đề cập đến nó trong phần bình luận bên dưới và chúng tôi sẽ liên hệ lại với bạn trong thời gian sớm nhất.