*
tìm kiếm kiếm tuyến tính với tìm tìm nhị phân là hai phương thức được sử dụng trong các mảng nhằm tìm kiếm các phần tử. Tìm kiếm là một quy 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ứ trường đoản cú hoặc ngẫu nhiên.

Bạn đang xem: Thuật toán tìm kiếm tuyến tính

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

Một điểm khác biệt giữa hai vấn đề này là gồm một đk tiên quyết mang đến tìm kiếm nhị phân, nghĩa là những yếu tố phải được sắp xếp trong lúc tìm kiếm tuyến đường tính không tồn tại điều kiện tiên quyết như vậy. Tuy nhiên cả hai phương thức tìm kiếm phần đông sử dụng những kỹ thuật khác nhau được bàn thảo dưới đây.

Biểu đồ so sánh

Cơ sở nhằm so sánhTìm kiếm tuyến đường 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 chổ chính giữa O (1)
Điều kiện tiên quyết cho một mảngKhông yêu cầuMảng bắt buộc theo vật dụng tự sắp xếp
Trường vừa lòng 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 singin 2 N so sánh
Có thể được tiến hành trênDanh sách mảng cùng liên kếtKhông thể được tiến hành trực tiếp trên list liên kết
Thao tác chènDễ dàng chèn vào thời gian cuối danh sáchYêu cầu cách xử lý để chèn tại vị trí tương thích của nó để gia hạn một list đượ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 trường đoản cú nhiên
Hữu íchDễ thực hiện và không cần ngẫu nhiên yếu tố nào.Dù sao thuật toán và các yếu tố phức hợp nên được tổ chức triển khai theo vật dụng tự.
Dòng mãÍt hơnHơn

Định nghĩa của kiếm tìm kiếm đường tính

Trong search kiếm con đường tính, từng phần tử của một mảng được tầm nã xuất từng dòng một theo đồ vật tự súc tích và kiểm soát xem nó có phải là thành phần mong mong hay không. Một tra cứu kiếm sẽ không còn thành công nếu toàn bộ các nguyên tố được truy cập và không tìm kiếm thấy yếu ớt tố hy vọng muốn. Vào trường hòa hợp xấu nhất, số lượng trường phù hợp trung bình chúng ta có thể phải quét một nửa size của mảng (n / 2).

Do đó, tìm kiếm kiếm đường tính có thể được tư tưởng là kỹ thuật đi qua mảng một biện pháp tuần tự nhằm xác xác định trí của mục đã cho. Công tác được chuyển ra sau đây minh họa hutgiammo.comệc tìm kiếm kiếm 1 phần tử của mảng bằng tìm kiếm.

Hiệu quả của tra cứu kiếm đường tính

Tiêu thụ thời hạn hoặc số lượng so sánh được tiến hành khi tìm kiếm một bản ghi trong bảng tra cứu kiếm xác định tác dụng của kỹ thuật. Nếu phiên bản ghi hy vọng muốn xuất hiện ở vị trí trước tiên của bảng search kiếm, thì chỉ gồm một so sánh được thực hiện. Khi phiên bản ghi mong muốn là bản ghi cuối cùng, thì n cần so sánh. Nếu bạn dạng ghi sẽ xuất hiện thêm ở ở đâu đó trong bảng tìm kiếm, trung bình, số lượng so sánh vẫn là (n + 1/2). Công dụng trường vừa lòng xấu duy nhất của kỹ thuật này là O (n) là hutgiammo.comết tắt của sản phẩm công nghệ tự thực hiện.

Chương trình C nhằm tìm kiếm một trong những phần tử với kỹ thuật search kiếm đường 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", và n); printf ("Nhập số: n"); for (i = 0; i

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

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

Logic đằng sau kỹ thuật này được giới thiệu 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 đối chiếu với bộ phận được tìm kiếm.

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

Nếu thành phần là thành phần bắt buộc, thì kiếm tìm kiếm thành công.Khi phần tử bé dại hơn mục ao ước muốn, tiếp nối chỉ tìm kiếm nửa đầu của mảng.Nếu nó bự hơn thành phần mong muốn, thì kiếm tìm kiếm vào nửa sau của mảng.

Lặp lại công hutgiammo.comệc tương tự cho đến khi một nhân tố được kiếm tìm thấy hoặc hết sạch trong khu vực tìm kiếm. Vào thuật toán này, mỗi khi ăn mặc tích tìm kiếm kiếm giảm. Bởi đó, số lượng so sánh nhiều nhất là log (N + 1). Công dụng là, nó là 1 trong những thuật toán hiệu quả khi so sánh với tìm kiếm kiếm đường tính, tuy vậy mảng yêu cầu được thu xếp trước khi tiến hành tìm tìm nhị phân.


Chương trình C nhằm tìm 1 phần tử cùng với kỹ thuật tìm kiếm nhị phân.

#include void main () {int i, ăn uống xin, kết thúc, giữa, n, tìm kiếm kiếm, mảng <100>; printf ("Nhập số thành phần n"); quét ("% d", và n); printf ("Nhập số% d n", n); for (i = 0; i

Sự khác biệt chính thân Tìm kiếm tuyến đường tính cùng Tìm tìm nhị phân

Tìm kiếm con đường tính tất cả tính lặp đi tái diễn và áp dụng cách tiếp cận tuần tự. Phương diện khác, tìm kiếm kiếm nhị phân thực hiện phương thức phân chia và chinh phục.Độ tinh hutgiammo.com thời gian của tra cứu kiếm đường tính là O (N) trong những khi tìm kiếm nhị phân tất cả O (log 2 N).Thời gian trường hợp cực tốt trong tra cứu kiếm tuyến đường tính là cho bộ phận đầu tiên, tức là O (1). Ngược lại, trong kiếm tìm kiếm nhị phân, nó dành riêng cho thành phần ở giữa, có nghĩa là O (1).Trong tra cứu kiếm đường tính, trường vừa lòng xấu nhất nhằm tìm kiếm một phần tử là N số so sánh. Ngược lại, sẽ là log 2 N số đối chiếu cho search kiếm nhị phân.Tìm kiếm đường tính có thể được triển khai trong một mảng cũng tương tự trong danh sách được liên kết trong khi tìm kiếm nhị phân cần thiết được thực hiện trực tiếp trên list được liên kết.Như họ biết search kiếm nhị phân yêu mong mảng được thu xếp là lý do Nó yêu cầu giải pháp xử lý để chèn vào vị trí tương thích của nó để gia hạn danh sách được sắp tới xếp. Ngược lại, tìm kiếm kiếm con đường tính không yêu cầu các yếu tố được sắp xếp, vày vậy những yếu tố tiện lợi được chèn vào cuối danh sách.Tìm kiếm tuyến tính rất giản đơn sử dụng với không cần ngẫu nhiên yếu tố nào. Mặt khác, thuật toán tìm kiếm nhị phân mặc dù rất cực nhọc và các yếu tố độc nhất vô nhị thiết buộc phải được thu xếp theo sản phẩm công nghệ tự.

Phần tóm lại

Cả nhì thuật toán kiếm tìm kiếm con đường tính và nhị phân hoàn toàn có thể hữu ích tùy ở trong vào ứng dụng. Lúc một mảng là cấu trúc dữ liệu cùng các bộ phận được thu xếp theo lắp thêm tự được sắp đến xếp, thì search kiếm nhị phân được ưu tiên để tìm tìm nhanh . Nếu list được liên kết là kết cấu dữ liệu bất kỳ các thành phần được sắp tới xếp như thế nào, tìm kiếm kiếm tuyến đường tính được đồng ý do không có công dụng thực hiện nay trực tiếp thuật toán search kiếm nhị phân.

Xem thêm: Nội Dung Quy Luật Phân Li Độc Lập, Quy Luật Phân Li Độc Lập Hay, Chi Tiết

Thuật toán search kiếm nhị phân nổi bật không thể được áp dụng cho danh sách được link vì list được links có thực chất động với không biết phần tử ở giữa thực sự được gán nghỉ ngơi đâu. Bởi đó, gồm một yêu cầu để kiến tạo biến thể của thuật toán kiếm tìm kiếm nhị phân cũng có thể vận động trên list được liên kết vì kiếm tìm kiếm nhị phân thực hiện nhanh hơn so với kiếm tìm kiếm đường tính.