Chuỗi tìm kiếm nhị phân JavaScript

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

Bạn có thể sử dụng tìm kiếm nhị phân cho các chuỗi không?

Làm cách nào để viết JavaScript tìm kiếm nhị phân?

JavaScript có phương pháp tìm kiếm nhị phân không?

Thuật toán tìm kiếm chuỗi nhanh nhất trong JavaScript là gì?