- vừa được xem lúc

Thuật toán Binary Search, tìm kiếm nhị phân! Implement code

0 0 32

Người đăng: Nguyễn Đức Thảo

Theo Viblo Asia

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à leftright
  • Phần tử đứng ở giữa leftRight đượ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

image.png

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!

Bình luận

Bài viết tương tự

- vừa được xem lúc

Tổng hợp các bài hướng dẫn về Design Pattern - 23 mẫu cơ bản của GoF

Link bài viết gốc: https://gpcoder.com/4164-gioi-thieu-design-patterns/. Design Patterns là gì. Design Patterns không phải là ngôn ngữ cụ thể nào cả.

0 0 296

- vừa được xem lúc

Học Spring Boot bắt đầu từ đâu?

1. Giới thiệu Spring Boot. 1.1.

0 0 271

- vừa được xem lúc

Cần chuẩn bị gì để bắt đầu học Java

Cần chuẩn bị những gì để bắt đầu lập trình Java. 1.1. Cài JDK hay JRE.

0 0 49

- vừa được xem lúc

Sử dụng ModelMapper trong Spring Boot

Bài hôm nay sẽ là cách sử dụng thư viện ModelMapper để mapping qua lại giữa các object trong Spring nhé. Trang chủ của ModelMapper đây http://modelmapper.org/, đọc rất dễ hiểu dành cho các bạn muốn tìm hiểu sâu hơn. 1.

0 0 192

- vừa được xem lúc

[Java] 1 vài tip nhỏ khi sử dụng String hoặc Collection part 1

. Hello các bạn, hôm nay mình sẽ chia sẻ về mẹo check String null hay full space một cách tiện lợi. Mình sẽ sử dụng thư viện Lớp StringUtils download file jar để import vào thư viện tại (link).

0 0 69

- vừa được xem lúc

Deep Learning với Java - Tại sao không?

Muốn tìm hiểu về Machine Learning / Deep Learning nhưng với background là Java thì sẽ như thế nào và bắt đầu từ đâu? Để tìm được câu trả lời, hãy đọc bài viết này - có thể kỹ năng Java vốn có sẽ giúp bạn có những chuyến phiêu lưu thú vị. DJL là tên viết tắt của Deep Java Library - một thư viện mã ng

0 0 137