Xin chào bét fờ zen!
Tình hình là hôm lay mình lên bài đầu tiên của seri Dốt toán học thuật toán của mình!
Như mình cũng đã nói ở rất nhiều bài viết của mình là: những kiến thức mình chia sẻ đều là do mình học hỏi và trải nghiệm, nên nếu có sai hoặc thiếu thì các bạn có thể đóng góp vào phía bên dưới để mọi người cùng tham khảo nhé!
Bắt đầu
Như tiêu đề! hôm nay chúng ta cùng tìm hiểu về một thuật toán cơ bản mà mình nghĩ lập trình viên nào cũng phải biết, đó là thuật toán Tìm kiếm nhị phân (Binary search)!
Chúng ta cùng bắt đầu luôn nhé!
Khái niệm
- Tìm kiếm nhị phân là một thuật toán tìm kiếm được sử dụng trong một mảng đã được sắp xếp bằng cách chia đôi mảng cần tìm kiếm nhiều lần .
- Chúng ta chia đôi mảng và gọi 2 phần chia đôi đó là left và right
- Phần tử đứng ở giữa left và Right được gọi là Mid
- Chúng ta sẽ dựa vào Mid để tìm xem giá trị chúng ta cần tìm nó nằm trên mảng left hay right
- Nếu giá trị cần tìm nằm ở trên left thì chúng ta sẽ loại bỏ mảng right và chỉ thực hiện tìm kiếm trên left
Với việc chỉ tìm kiếm trên left hoặc right thì thuật toán Binary search sẽ có performace nhanh hơn đáng kế so với thuật toán Tìm kiếm tuyến tính Vì thuật toán Tìm kiếm tuyến tính sẽ phải lặp qua các phần tử để thực hiện tìm kiếm!
Các bước thực hiện
- Bước 1: Cho 1 mảng arr[] số nguyên đã được sắp xếp và x là giá trị cần tìm
- Bước 2: Thực hiện tách mảng ra làm 2 và tìm phần tử ở giữa mảng và gọi nó là mid, công thức tính (Mid = (left + right)/2)
- Bước 3:
- Nếu arr[mid] == x thì sẽ return ra mid - Ngược lại nếu arr[mid] > x thì right = mid - 1 vì giá trị cần tìm chắc chắn ko nằm trên right nên ta sẽ loại bỏ nó! và thực hiện tìm kiếm -
- Ngược lại nếu arr[mid] < x thì left = mid + 1 vì giá trị cần tìm chắc chắn ko nằm trên left nên ta sẽ loại bỏ nó! và thực hiện tìm kiếm
Implement code
Mình sẽ để console trong từng bước lặp để các bạn thấy rõ hơn và hiểu hơn nhé!
public class BinarySearch { public static void main(String[] args) { int arr[] = {1,2,3,4,5,6,7,8,9}; System.out.println(binary(arr,4)); } public static int binary(int a[], int x){ int left = 0; int right = a.length - 1; for (int i = left; i <= right; i++){ System.out.println(" vòng "+(i+1)+" left = "+left); System.out.println(" vòng "+(i+1)+" right = "+right); int mid = (left + right)/2; System.out.println(" vòng "+(i+1)+" mid = "+mid); System.out.println(" vòng "+(i+1)+" a[mid] = "+a[mid]); System.out.println("------------------------------"); if(a[mid] == x){ return mid; }else if(a[mid] > x){ right = mid - 1; } else { left = mid + 1; } } return -1; }
} Mình thực hiện tìm giá trị x = 4 trên mảng arr[]!
Mình sử dụng for và điều kiện dừng vòng lặp là left <= right
Và nếu không tìm thấy giá trị cần tìm trên mảng thì sẽ return ra -1
Và kết quả sau khi chạy chương trình!
vòng 2 left = 0 vòng 2 right = 3 vòng 2 mid = 1 vòng 2 a[mid] = 2
------------------------------ vòng 3 left = 2 vòng 3 right = 3 vòng 3 mid = 2 vòng 3 a[mid] = 3
------------------------------ vòng 4 left = 3 vòng 4 right = 3 vòng 4 mid = 3 vòng 4 a[mid] = 4
------------------------------
Giá trị cần tìm nằm ở index = 3
Các bạn coppy code và chạy sau đó tự phân tích và cảm nhận nhé, vì nếu các bạn chỉ đọc và không thực hành nó thì sẽ rất khó để nhớ kiến thức!
Kết
OTOKE! Vừa rồi chúng ta đã cùng tìm hiểu thuật toán Binart search và các bước nó hoạt động ra sao rùi đúng khum!
Với bài viết này, mình mong các bạn có thể hiểu được nó và áp dụng nó trong công việc hàng ngày của mình nhé!, xin chào!