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

[trieu.dev.da]

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à ngược lại!

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 1 left = 0
vòng 1 right = 8
vòng 1 mid = 4
vòng 1 a[mid] = 5
------------------------------
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