Cách phát triên thuật toán tìm kiếm nhị phân

Tìm kiếm tuyến tính trong Java luôn là phương pháp tiếp theo để tìm một phần tử trong một mảng. Nó tìm kiếm từng phần tử của mảng một cách tuần tự và cực kỳ dễ thực hiện. Tuy nhiên, những thiếu sót của Tìm kiếm tuyến tính là rõ ràng khi mảng được đề cập chứa hàng chục nghìn phần tử. Trong những trường hợp như vậy, phương pháp “chia để trị” do Tìm kiếm nhị phân triển khai sẽ hiệu quả hơn rất nhiều và thích hợp hơn cho các lập trình viên có tính đến sự phức tạp về thời gian và không gian.

Tìm kiếm nhị phân

Trong Tìm kiếm nhị phân, một mảng được chia liên tục thành hai nửa cho đến khi tìm thấy khóa (phần tử đang được tìm kiếm). Việc phân chia là ảo tức là tính toàn vẹn của dữ liệu được duy trì. Với mỗi lần lặp lại, giá trị ở giữa của mảng được tập trung. Nếu giá trị bằng với khóa mà chúng ta đang tìm kiếm, vòng lặp hoặc hàm đệ quy sẽ kết thúc. Nếu không, nó tiếp tục lặp lại. Nếu giá trị ở giữa lớn hơn khóa, thì hàm sẽ tập trung vào nửa đầu của mảng và ngược lại. Quá trình này được lặp lại cho đến khi tìm thấy khóa hoặc toàn bộ mảng đã được lặp lại.

Sự khác biệt giữa tìm kiếm tuyến tính và nhị phân

Tìm kiếm tuyến tính Tìm kiếm nhị phân Tìm kiếm tuần tự trong mảng Chia mảng thành hai nửa cho đến khi tìm thấy giá trị Hoạt động với bất kỳ mảng nào Chỉ hoạt động với các mảng được sắp xếp Độ phức tạp là O(N) Độ phức tạp là O(log2N) Có thể làm việc trên các mảng được sắp xếp và chưa sắp xếp Chỉ có thể được thực hiện trên các mảng được sắp xếp. Ít phức tạp hơn để thực hiện Phức tạp hơn để thực hiện

Thuật toán tìm kiếm nhị phân

Thuật toán tìm kiếm nhị phân được đưa ra dưới đây.

1. Xác định điểm đầu và điểm cuối của mảng. Các điểm sẽ được điều chỉnh ở mỗi lần lặp theo mảng và khóa được tìm kiếm.
2. Lặp lại mảng và so sánh giá trị giữa giữa điểm đầu tiên và điểm cuối cùng hiện tại của bạn. Trong lần lặp đầu tiên, biến đầu tiên và biến cuối cùng sẽ giống với biến thực trong mảng.
3. Nếu khóa lớn hơn giá trị ở giữa, chỉ mục của giá trị đó sẽ được lưu trữ trong biến "Đầu tiên" mới.
4. Nếu khóa nhỏ hơn giá trị ở giữa, chỉ mục của giá trị đó sẽ được lưu trong biến 'Cuối cùng'.
5. Điều kiện này được lặp lại cho đến khi một trong hai điều kiện trở thành sự thật:
   • Đã tìm thấy chìa khóa.
   • Toàn bộ mảng đã được lặp lại.

Mã cho cả tìm kiếm nhị phân lặp và tìm kiếm nhị phân đệ quy được đưa ra dưới đây.

Tìm kiếm nhị phân lặp đi lặp lại

Mã cho Tìm kiếm nhị phân bằng phương pháp lặp được cung cấp bên dưới.

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;
    }
}

Tìm kiếm nhị phân đệ quy

Mã cho nhị phân sử dụng đệ quy được đưa ra dưới đây.

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);
    }
}

Thời gian phức tạp

Với mỗi lần lặp lại, mảng tức là không gian tìm kiếm được chia một nửa. Sau mỗi lần lặp lại 'm', không gian tìm kiếm sẽ thay đổi thành kích thước N/2m. Trong trường hợp xấu nhất, chúng ta sẽ chỉ còn lại một phần tử ở một phía xa của mảng. Lúc này độ phức tạp của tìm kiếm nhị phân sẽ là k = log2N. Độ phức tạp thời gian của tìm kiếm tuyến tính là O(N) dẫn đến tìm kiếm nhị phân nhanh hơn nhiều với độ phức tạp O(log2N). Đây là lợi ích chính của việc sử dụng tìm kiếm nhị phân so với tìm kiếm tuyến tính.

Độ phức tạp không gian

Tìm kiếm nhị phân sử dụng ba biến khác nhau - bắt đầu, kết thúc và giữa. Ba biến này được tạo dưới dạng con trỏ trỏ đến vị trí bộ nhớ của các chỉ số mảng. Do đó, tìm kiếm nhị phân cực kỳ hiệu quả với không gian. Độ phức tạp không gian của tìm kiếm nhị phân lặp là O(1). Để thực hiện đệ quy, nó là O(log N).