Thuật toán tìm kiếm – Tìm kiếm tuyến tính và triển khai mã tìm kiếm nhị phân và phân tích độ phức tạp

Thuật toán tìm kiếm là một khái niệm khoa học máy tính cơ bản mà bạn nên hiểu với tư cách là một nhà phát triển. Chúng hoạt động bằng cách sử dụng phương pháp từng bước để định vị dữ liệu cụ thể giữa một bộ sưu tập dữ liệu.

Trong bài viết này, chúng ta sẽ tìm hiểu cách các thuật toán tìm kiếm hoạt động bằng cách xem xét các triển khai của chúng trong Java và Python.

Thuật toán tìm kiếm là gì?

Theo Wikipedia, một thuật toán tìm kiếm là:

Bất kỳ thuật toán nào giải quyết vấn đề tìm kiếm, cụ thể là, để truy xuất thông tin được lưu trữ trong một số cấu trúc dữ liệu hoặc được tính toán trong không gian tìm kiếm của miền vấn đề, với các giá trị rời rạc hoặc liên tục.

Các thuật toán tìm kiếm được thiết kế để kiểm tra hoặc truy xuất một phần tử từ bất kỳ cấu trúc dữ liệu nào mà phần tử đó đang được lưu trữ. Họ tìm kiếm mục tiêu (chìa khóa) trong không gian tìm kiếm.

Các loại thuật toán tìm kiếm

Trong bài đăng này, chúng ta sẽ thảo luận về hai loại thuật toán tìm kiếm quan trọng:

  1. Tìm kiếm tuyến tính hoặc tuần tự
  2. Tìm kiếm nhị phân

Hãy thảo luận chi tiết về hai điều này với các ví dụ, cách triển khai mã và phân tích độ phức tạp về thời gian.

Thuật toán này hoạt động bằng cách lặp lại tuần tự qua toàn bộ mảng hoặc danh sách từ một đầu cho đến khi phần tử đích được tìm thấy. Nếu phần tử được tìm thấy, nó trả về chỉ mục của nó, khác -1.

Bây giờ chúng ta hãy xem xét một ví dụ và cố gắng hiểu nó hoạt động như thế nào:

arr = [2, 12, 15, 11, 7, 19, 45]

Giả sử phần tử mục tiêu chúng ta muốn tìm kiếm là 7.

  • Bắt đầu với chỉ số 0 và so sánh từng phần tử với mục tiêu
  • Nếu mục tiêu được tìm thấy bằng với phần tử, hãy trả về chỉ mục của nó
  • Nếu mục tiêu không được tìm thấy, trả về -1

Triển khai mã

Bây giờ chúng ta hãy xem cách chúng ta sẽ triển khai loại thuật toán tìm kiếm này bằng một vài ngôn ngữ lập trình khác nhau.

Tìm kiếm tuyến tính hoặc tuần tự trong Java

package algorithms.searching;

public class LinearSearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 11, 7, 19, 45};
        int target = 7;
        System.out.println(search(nums, target));

    }

    static int search(int[] nums, int target) {
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] == target) {
                return index;
            }
        }
        return -1;
    }
}

Tìm kiếm tuyến tính hoặc tuần tự bằng Python

def search(nums, target):
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1

if __name__ == '__main__':
    nums = [2, 12, 15, 11, 7, 19, 45]
    target = 7
    print(search(nums, target))

Phân tích độ phức tạp về thời gian

Trường hợp tốt nhất xảy ra khi phần tử đích là phần tử đầu tiên của mảng. Số phép so sánh, trong trường hợp này, là 1. Vì vậy, độ phức tạp về thời gian là O(1).

Trường hợp trung bình: Trung bình, phần tử đích sẽ ở đâu đó ở giữa mảng. Số lượng so sánh, trong trường hợp này, sẽ là N / 2. Vì vậy, độ phức tạp về thời gian sẽ là O(N) (hằng số bị bỏ qua).

Trường hợp xấu nhất xảy ra khi phần tử đích là phần tử cuối cùng trong mảng hoặc không có trong mảng. Trong trường hợp này, chúng ta phải duyệt qua toàn bộ mảng và do đó số lượng phép so sánh sẽ là N. Vì vậy, độ phức tạp về thời gian sẽ là O(N).

Loại thuật toán tìm kiếm này được sử dụng để tìm vị trí của một giá trị cụ thể chứa trong một mảng được sắp xếp. Thuật toán tìm kiếm nhị phân hoạt động trên nguyên tắc chia để trị và nó được coi là thuật toán tìm kiếm tốt nhất vì nó chạy nhanh hơn.

Bây giờ, hãy lấy một mảng đã sắp xếp làm ví dụ và cố gắng hiểu cách hoạt động của nó:

arr = [2, 12, 15, 17, 27, 29, 45]

Giả sử phần tử mục tiêu được tìm kiếm là 17.

  • So sánh phần tử đích với phần tử giữa của mảng.
  • Nếu phần tử đích lớn hơn phần tử ở giữa, thì việc tìm kiếm sẽ tiếp tục ở nửa bên phải.
  • Ngược lại, nếu phần tử đích nhỏ hơn giá trị giữa, tìm kiếm sẽ tiếp tục ở nửa bên trái.
  • Quá trình này được lặp lại cho đến khi phần tử ở giữa bằng với phần tử đích hoặc phần tử đích không có trong mảng
  • Nếu phần tử đích được tìm thấy, chỉ mục của nó được trả về, ngược lại -1 được trả về.

Triển khai mã

Tìm kiếm nhị phân trong Java

package algorithms.searching;

public class BinarySearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 17, 27, 29, 45};
        int target = 17;
        System.out.println(search(nums, target));
    }

    static int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (nums[mid] > target)
                end = mid - 1;
            else if (nums[mid] < target)
                start = mid + 1;
            else
                return mid;
        }
        return -1;
    }
}

Tìm kiếm nhị phân trong Python

def search(nums, target):
    start = 0
    end = len(nums)-1

    while start <= end:
        mid = start + (end-start)//2


        if nums[mid] > target:
            end = mid-1
        elif nums[mid] < target:
            start = mid+1
        else:
            return mid

    return -1


if __name__ == '__main__':
    nums = [2, 12, 15, 17, 27, 29, 45]
    target = 17
    print(search(nums, target))

Phân tích độ phức tạp về thời gian

Trường hợp tốt nhất xảy ra khi phần tử đích là phần tử giữa của mảng. Số phép so sánh, trong trường hợp này, là 1. Vì vậy, độ phức tạp về thời gian là O(1).

Trường hợp trung bình: Trung bình, phần tử đích sẽ ở đâu đó trong mảng. Vì vậy, độ phức tạp về thời gian sẽ là O(logN).

Trường hợp xấu nhất xảy ra khi phần tử đích không có trong danh sách hoặc nó ở cách xa phần tử giữa. Vì vậy, độ phức tạp về thời gian sẽ là O(logN).

Cách tính độ phức tạp về thời gian:

Giả sử quá trình lặp lại trong Tìm kiếm nhị phân kết thúc sau k các lần lặp lại.

Ở mỗi lần lặp, mảng được chia một nửa. Vì vậy, giả sử độ dài của mảng tại bất kỳ lần lặp nào là n.

Tại Lặp lại 1,

Length of array = N

Tại Lặp lại 2,

Length of array = N/2

Tại Lặp lại 3,

Length of array = (N/2)/2 = N/2^2

Tại Lặp lại k,

Length of array = N/2^k

Ngoài ra, chúng ta biết rằng sau k lần phân chia, độ dài của mảng trở thành 1: Độ dài của mảng = N⁄2k = 1=> N = 2k

Nếu chúng ta áp dụng một hàm nhật ký cho cả hai bên: khúc gỗ2 (N) = nhật ký2 (2k)=> khúc gỗ2 (N) = k log2 (2)

Như (nhật kýMột (a) = 1)
Do đó, => k = log2 (N)

Vì vậy, bây giờ chúng ta có thể hiểu tại sao độ phức tạp về thời gian của Tìm kiếm nhị phân là nhật ký2 (N).

Bạn cũng có thể hình dung hai thuật toán trên bằng cách sử dụng công cụ đơn giản được xây dựng bởi Dipesh PatilTrình hiển thị thuật toán.

Giả sử, chúng ta phải tìm một phần tử đích trong một mảng đã sắp xếp. Chúng ta biết rằng mảng được sắp xếp, nhưng chúng ta không biết liệu nó được sắp xếp theo thứ tự tăng dần hay giảm dần.

Việc triển khai tương tự như tìm kiếm nhị phân ngoại trừ việc chúng ta cần xác định xem mảng được sắp xếp theo thứ tự tăng dần hay giảm dần. Sau đó, điều này cho phép chúng tôi đưa ra quyết định tiếp tục tìm kiếm ở nửa bên trái của mảng hay nửa bên phải của mảng.

  • Đầu tiên, chúng tôi so sánh mục tiêu với phần tử ở giữa
  • Nếu mảng được sắp xếp theo thứ tự tăng dần và mục tiêu nhỏ hơn phần tử ở giữa HOẶC LÀ mảng được sắp xếp theo thứ tự giảm dần và mục tiêu lớn hơn phần tử ở giữa, sau đó chúng tôi tiếp tục tìm kiếm ở nửa dưới của mảng bằng cách thiết lập end=mid-1.
  • Nếu không, chúng tôi thực hiện tìm kiếm ở nửa trên của mảng bằng cách đặt start=mid+1

Điều duy nhất chúng ta cần làm là tìm hiểu xem mảng được sắp xếp theo thứ tự tăng dần hay giảm dần. Chúng ta có thể dễ dàng tìm thấy điều này bằng cách so sánh các phần tử đầu tiên và cuối cùng của mảng.

if arr[0] < arr[arr.length-1]
    array is sorted in ascending order 
else
    array is sorted in descending order

Triển khai mã

Tìm kiếm nhị phân theo thứ tự bất khả tri trong Java

package algorithms.searching;

public class OrderAgnosticBinarySearch {
    public static void main(String[] args) {
        int[] nums1 = {-1, 2, 4, 6, 7, 8, 12, 15, 19, 32, 45, 67, 99};
        int[] nums2 = {99, 67, 45, 32, 19, 15, 12, 8, 7, 6, 4, 2, -1};
        int target = -1;
        System.out.println(search(nums1, target));
        System.out.println(search(nums2, target));
    }

    static int search(int[] arr, int target) {
        int start = 0;
        int end = arr.length - 1;

        boolean isAscending = arr[start] < arr[end];

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (target == arr[mid])
                return mid;

            if (isAscending) {
                if (target < arr[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else {
                if (target < arr[mid]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }


}

Tìm kiếm nhị phân theo thứ tự bất khả tri trong Python

def search(nums, target):
    start = 0
    end = len(nums)-1

    is_ascending = nums[start] < nums[end]

    while start <= end:
        mid = start + (end-start)//2

        if target == nums[mid]:
            return mid

        if is_ascending:
            if target < nums[mid]:
                end = mid-1
            else:
                start = mid+1
        else:
            if target < nums[mid]:
                start = mid+1
            else:
                end = mid-1

    return -1


if __name__ == '__main__':
    nums1 = [-1, 2, 4, 6, 7, 8, 12, 15, 19, 32, 45, 67, 99]
    nums2 = [99, 67, 45, 32, 19, 15, 12, 8, 7, 6, 4, 2, -1]
    target = -1
    print(search(nums1, target))
    print(search(nums2, target))

Phân tích độ phức tạp về thời gian

Sẽ không có sự thay đổi về độ phức tạp về thời gian, vì vậy nó sẽ giống với Tìm kiếm nhị phân.

Trong bài viết này, chúng tôi đã thảo luận về hai thuật toán tìm kiếm quan trọng nhất cùng với việc triển khai mã của chúng trong Python và Java. Chúng tôi cũng đã xem xét phân tích độ phức tạp về thời gian của họ.

Cảm ơn vì đã đọc!

Đăng ký nhận bản tin của tôi

Thanks for Reading

Enjoyed this post? Share it with your networks.

Get more stuff

Subscribe to our mailing list and get interesting stuff and updates to your email inbox.

Thank you for subscribing.

Something went wrong.

Leave a Feedback!