Chúng ta thường cần tìm một mục dữ liệu cụ thể trong số hàng trăm, hàng nghìn, hàng triệu hoặc thậm chí nhiều hơn. Chẳng hạn, chúng tôi có thể muốn tìm số điện thoại của ai đó trong điện thoại của mình hoặc một địa chỉ cụ thể ở một quốc gia. Đây là lý do tại sao các thuật toán tìm kiếm có ích
Nếu không có thuật toán tìm kiếm, bạn sẽ cần xem xét từng dữ liệu riêng lẻ để tìm dữ liệu bạn đang tìm kiếm. Khi dữ liệu trở nên lớn hơn, việc xem xét từng dữ liệu để tìm mục tiêu sẽ không hiệu quả
Sự thật thú vị
“Nếu tất cả các tên trên thế giới được viết ra cùng nhau theo thứ tự và bạn muốn tìm kiếm vị trí của một tên cụ thể, tìm kiếm nhị phân sẽ thực hiện việc này trong tối đa 35 lần lặp lại. ” (Hackerearth. com)
Có nhiều loại thuật toán tìm kiếm, chẳng hạn như tìm kiếm tuyến tính, tìm kiếm theo cấp số nhân, v.v. Hôm nay chúng ta sẽ khám phá thuật toán tìm kiếm hiệu quả hơn khi xử lý một tập dữ liệu lớn, Tìm kiếm nhị phân
Tìm kiếm nhị phân thường được sử dụng trên mảng, nhưng để sử dụng tìm kiếm nhị phân, mảng phải được sắp xếp. Nó hoạt động bằng cách so sánh giá trị trung bình của mảng chứa giá trị trung bình của tập dữ liệu với mục tiêu mà chúng tôi đang tìm kiếm
Đó cũng là một cách thực hành tốt để xác định các chức năng tập trung vào một mục tiêu. Sẽ hợp lý hơn nếu xác định một hàm để sắp xếp, sau đó gọi hàm tìm kiếm nhị phân để tìm kiếm
Trước khi đi sâu vào mã, hãy xem qua các bước tìm kiếm nhị phân
1. Tìm điểm bắt đầu và điểm kết thúc của mảng, thường được gọi là điểm thấp và điểm cao. Thấp sẽ là chỉ số 0, cao sẽ là kích thước của mảng trừ 1. Trong khoa học máy tính, chúng tôi đếm chỉ số từ 0 và các phần tử từ 1, vì vậy chỉ số cuối cùng của mảng thường sẽ là n trừ 1, với n là kích thước của mảng
2. Tìm trung vị của mảng. Điều này có thể được thực hiện bằng cách thực hiện (thấp + cao) / 2
3. So sánh mục tiêu tìm kiếm với trung vị, nếu chúng khớp nhau, chúng tôi đã tìm thấy mục tiêu và chỉ cần trả lại chỉ mục. Đây còn được gọi là trường hợp tốt nhất
4. Nếu mục tiêu nhỏ hơn trung vị, điều đó có nghĩa là bất kỳ thứ gì lớn hơn trung vị cũng sẽ lớn hơn mục tiêu, vì vậy chúng ta có thể bỏ qua những mục tiêu đó. Chúng tôi làm điều này bằng cách giảm chỉ số giới hạn trên, cập nhật nó thành trung vị trừ 1, vì trung vị cũng được so sánh và có thể bỏ qua
5. Tương tự, nếu mục tiêu lớn hơn trung vị, chúng ta sẽ tăng cận dưới, cập nhật nó thành trung vị + 1
6. Lặp lại các bước trên cho đến khi tìm thấy mục tiêu hoặc tất cả các số đã được kiểm tra
Bây giờ chúng ta hãy xem ví dụ sau
Chúng tôi đang cố gắng tìm kiếm 5 và lấy vị trí chỉ mục của nó nếu nó được tìm thấy
lần lặp đầu tiên
Kích thước của mảng = 13
thấp = 0
cao = 13–1 = 12
giữa = (0 + 13)/2 = 6
mục tiêu = 5
Trung bình không phù hợp với mục tiêu của chúng tôi. Trung vị lớn hơn mục tiêu nên nửa sau cũng như trung vị sẽ bị bỏ qua. Cập nhật chỉ số giới hạn trên là giữa 1
Bây giờ đối với lần lặp lại thứ hai, mức cao sẽ được cập nhật vì chúng tôi đang bỏ qua dữ liệu bằng hoặc lớn hơn mức trung bình
Lần lặp thứ 2
cao = 6–1 = 5
thấp = 0
giữa = (0+5)/2 = 2
Mục tiêu nhỏ hơn trung bình, bỏ qua nửa sau, cập nhật mức cao
Lần lặp thứ 3
thấp = 0
cao = 3–1 = 2
giữa = (0 + 2 ) / 2 = 1
mảng [mid] = 5 là mục tiêu của chúng tôi, vì vậy chỉ mục 1 sẽ được trả về
Đây là một ví dụ khác
Bây giờ hãy đi sâu vào mã
function BinarySearch(array, low, high, target){ //base condition // To exit the recursion, if array is empty or n = 1 if(low > high) {return -1;
} //calculate the midpoint of array let mid=Math.floor( (low+ high)/2) ;
if (target == array[mid]) { console.log('Target is found at index: ', mid) return mid; } else if (target < array[mid]) { //if the target is less the number at the midpoint of array
//Search the 2nd half. return BinarySearch(array, low, mid-1, target); } else { //if the target is larger number at the midpoint of array
//Search the 1st half. return BinarySearch(array, mid+1, high, target); }
}
// To test:
BinarySearch([1,5,7,8,9,10,15], 0, 6, 5)// Console:'Target is found at index: 1'
Độ phức tạp thời gian chạy của tìm kiếm nhị phân là O(logn), vì kích thước của dữ liệu được cắt thành một nửa sau mỗi lần lặp lại
Tại lần lặp 1 , chiều dài của mảng = n,
lần lặp 2, n = n/2
lần lặp 3, n = (n/2)/2
Sau lần lặp k, độ dài của mảng sẽ là n/2^k
Nếu bạn quan tâm đến độ phức tạp của thời gian, hãy xem liên kết này
https. //www. chuyên viên máy tính. org/phân tích độ phức tạp của tìm kiếm nhị phân/
Bạn cũng có thể tự hỏi tìm kiếm nhị phân được sử dụng như thế nào trong cuộc sống thực. Hãy xem video này, đây là một ví dụ tuyệt vời về cách tìm kiếm nhị phân có thể trở nên thiết thực