Đề XuấT, 2024

Editor Choice

Sự khác biệt giữa Tìm kiếm tuyến tính và Tìm kiếm nhị phân

Tìm kiếm tuyến tính và tìm kiếm nhị phân là hai phương thức được sử dụng trong các mảng để tìm kiếm các phần tử. Tìm kiếm là một quá trình tìm kiếm một yếu tố trong danh sách các yếu tố được lưu trữ theo bất kỳ thứ tự hoặc ngẫu nhiên.

Sự khác biệt chính giữa tìm kiếm tuyến tính và tìm kiếm nhị phân là tìm kiếm nhị phân mất ít thời gian hơn để tìm kiếm một phần tử từ danh sách các phần tử được sắp xếp. Vì vậy, suy ra rằng hiệu quả của phương pháp tìm kiếm nhị phân lớn hơn tìm kiếm tuyến tính.

Một điểm khác biệt giữa hai điều này là có một điều kiện tiên quyết cho tìm kiếm nhị phân, nghĩa là các yếu tố phải được sắp xếp trong khi tìm kiếm tuyến tính không có điều kiện tiên quyết như vậy. Mặc dù cả hai phương pháp tìm kiếm đều sử dụng các kỹ thuật khác nhau được thảo luận dưới đây.

Biểu đồ so sánh

Cơ sở để so sánhTìm kiếm tuyến tínhTìm kiếm nhị phân
Độ phức tạp thời gianTRÊN)O (log 2 N)
Thời gian tốt nhấtPhần tử thứ nhất O (1)Phần tử trung tâm O (1)
Điều kiện tiên quyết cho một mảngKhông yêu cầuMảng phải theo thứ tự sắp xếp
Trường hợp xấu nhất cho số lượng phần tử NN so sánh là bắt buộcCó thể kết luận chỉ sau khi đăng nhập 2 N so sánh
Có thể được thực hiện trênDanh sách mảng và liên kếtKhông thể được thực hiện trực tiếp trên danh sách liên kết
Thao tác chènDễ dàng chèn vào cuối danh sáchYêu cầu xử lý để chèn tại vị trí thích hợp của nó để duy trì một danh sách được sắp xếp.
Loại thuật toánLặp đi lặp lại trong tự nhiênChia rẽ và chinh phục trong tự nhiên
Hữu íchDễ sử dụng và không cần bất kỳ yếu tố nào.Dù sao thuật toán và các yếu tố phức tạp nên được tổ chức theo thứ tự.
Dòng mãÍt hơnHơn

Định nghĩa của Tìm kiếm tuyến tính

Trong tìm kiếm tuyến tính, từng phần tử của một mảng được truy xuất từng cái một theo thứ tự logic và kiểm tra xem nó có phải là phần tử mong muốn hay không. Một tìm kiếm sẽ không thành công nếu tất cả các yếu tố được truy cập và không tìm thấy yếu tố mong muốn. Trong trường hợp xấu nhất, số lượng trường hợp trung bình chúng ta có thể phải quét một nửa kích thước của mảng (n / 2).

Do đó, tìm kiếm tuyến tính có thể được định nghĩa là kỹ thuật đi qua mảng một cách tuần tự để xác định vị trí của mục đã cho. Chương trình được đưa ra dưới đây minh họa việc tìm kiếm một phần tử của mảng bằng tìm kiếm.

Hiệu quả của tìm kiếm tuyến tính

Tiêu thụ thời gian hoặc số lượng so sánh được thực hiện khi tìm kiếm một bản ghi trong bảng tìm kiếm xác định hiệu quả của kỹ thuật. Nếu bản ghi mong muốn có mặt ở vị trí đầu tiên của bảng tìm kiếm, thì chỉ có một so sánh được thực hiện. Khi bản ghi mong muốn là bản ghi cuối cùng, thì n phải so sánh. Nếu bản ghi sẽ xuất hiện ở đâu đó trong bảng tìm kiếm, trung bình, số lượng so sánh sẽ là (n + 1/2). Hiệu quả trường hợp xấu nhất của kỹ thuật này là O (n) là viết tắt của thứ tự thực hiện.

Chương trình C để tìm kiếm một phần tử với kỹ thuật tìm kiếm tuyến tính.

 #include #include void main () {int a [100], n, i, item, loc = -1; clrscr (); printf ("\ nNhập số phần tử:"); quét ("% d", & n); printf ("Nhập số: \ n"); for (i = 0; i <= n-1; i ++) {scanf ("% d", & a [i]); } printf ("\ nNhập số cần tìm:"); quétf ("% d", & mục); for (i = 0; i = 0) {printf ("\ n% d được tìm thấy ở vị trí% d:", item, loc + 1); } other {printf ("\ n Mục không tồn tại"); } getch (); } 

Định nghĩa tìm kiếm nhị phân

Tìm kiếm nhị phân là một thuật toán cực kỳ hiệu quả. Kỹ thuật tìm kiếm này tiêu tốn ít thời gian hơn trong việc tìm kiếm vật phẩm đã cho trong các so sánh tối thiểu có thể. Để thực hiện tìm kiếm nhị phân, đầu tiên, chúng ta phải sắp xếp các phần tử mảng.

Logic đằng sau kỹ thuật này được đưa ra dưới đây:

  • Đầu tiên, tìm phần tử giữa của mảng.
  • Phần tử ở giữa của mảng được so sánh với phần tử được tìm kiếm.

Có ba trường hợp có thể phát sinh:

  1. Nếu phần tử là phần tử bắt buộc, thì tìm kiếm thành công.
  2. Khi phần tử nhỏ hơn mục mong muốn, sau đó chỉ tìm kiếm nửa đầu của mảng.
  3. Nếu nó lớn hơn phần tử mong muốn, thì tìm kiếm trong nửa sau của mảng.

Lặp lại các bước tương tự cho đến khi một yếu tố được tìm thấy hoặc cạn kiệt trong khu vực tìm kiếm. Trong thuật toán này, mỗi khi diện tích tìm kiếm giảm. Do đó, số lượng so sánh nhiều nhất là log (N + 1). Kết quả là, nó là một thuật toán hiệu quả khi so sánh với tìm kiếm tuyến tính, nhưng mảng phải được sắp xếp trước khi thực hiện tìm kiếm nhị phân.

Chương trình C để tìm một phần tử với kỹ thuật tìm kiếm nhị phân.

 #include void main () {int i, ăn xin, kết thúc, giữa, n, tìm kiếm, mảng [100]; printf ("Nhập số phần tử \ n"); quét ("% d", & n); printf ("Nhập số% d \ n", n); for (i = 0; i <n; i ++) scanf ("% d", & mảng [i]); printf ("Nhập số cần tìm kiếm \ n"); quét ("% d", & tìm kiếm); ăn xin = 0; kết thúc = n - 1; giữa = (ăn xin + kết thúc) / 2; while (beg <= end) {if (mảng [middle] end) printf ("Tìm kiếm không thành công!% d không có trong danh sách. \ n", tìm kiếm); getch (); } 

Sự khác biệt chính giữa Tìm kiếm tuyến tính và Tìm kiếm nhị phân

  1. Tìm kiếm tuyến tính có tính lặp đi lặp lại và sử dụng cách tiếp cận tuần tự. Mặt khác, tìm kiếm nhị phân thực hiện phương pháp phân chia và chinh phục.
  2. Độ phức tạp thời gian của tìm kiếm tuyến tính là O (N) trong khi tìm kiếm nhị phân có O (log 2 N).
  3. Thời gian trường hợp tốt nhất trong tìm kiếm tuyến tính là cho phần tử đầu tiên, tức là O (1). Ngược lại, trong tìm kiếm nhị phân, nó dành cho phần tử ở giữa, tức là O (1).
  4. Trong tìm kiếm tuyến tính, trường hợp xấu nhất để tìm kiếm một phần tử là N số so sánh. Ngược lại, đó là log 2 N số so sánh cho tìm kiếm nhị phân.
  5. Tìm kiếm tuyến tính có thể được thực hiện trong một mảng cũng như trong danh sách được liên kết trong khi tìm kiếm nhị phân không thể được thực hiện trực tiếp trên danh sách được liên kết.
  6. Như chúng ta biết Tìm kiếm nhị phân yêu cầu mảng được sắp xếp là lý do Nó yêu cầu xử lý để chèn vào vị trí thích hợp của nó để duy trì danh sách được sắp xếp. Ngược lại, tìm kiếm tuyến tính không yêu cầu các yếu tố được sắp xếp, vì vậy các yếu tố dễ dàng được chèn vào cuối danh sách.
  7. Tìm kiếm tuyến tính rất dễ sử dụng và không cần bất kỳ yếu tố nào. Mặt khác, thuật toán tìm kiếm nhị phân tuy nhiên rất khó và các yếu tố nhất thiết phải được sắp xếp theo thứ tự.

Phần kết luận

Cả hai thuật toán tìm kiếm tuyến tính và nhị phân có thể hữu ích tùy thuộc vào ứng dụng. Khi một mảng là cấu trúc dữ liệu và các phần tử được sắp xếp theo thứ tự được sắp xếp, thì tìm kiếm nhị phân được ưu tiên để tìm kiếm nhanh . Nếu danh sách được liên kết là cấu trúc dữ liệu bất kể các phần tử được sắp xếp như thế nào, tìm kiếm tuyến tính được chấp nhận do không có khả năng thực hiện trực tiếp thuật toán tìm kiếm nhị phân.

Thuật toán tìm kiếm nhị phân điển hình không thể được sử dụng cho danh sách được liên kết vì danh sách được liên kết có bản chất động và không biết phần tử ở giữa thực sự được gán ở đâu. Do đó, có một yêu cầu để thiết kế biến thể của thuật toán tìm kiếm nhị phân cũng có thể hoạt động trên danh sách được liên kết vì tìm kiếm nhị phân thực hiện nhanh hơn so với tìm kiếm tuyến tính.

Top