Tìm kiếm nhị phân là một trong những cách dễ dàng nhất để tìm một phần tử trong một mảng

Khá thường xuyên, lập trình, thậm chí cả người mới bắt đầu, đang phải đối mặt với thực tế là có một bộ số trong đó nó là cần thiết để tìm thấy một số nhất định. Bộ sưu tập này được gọi là mảng. Và để tìm ra yếu tố đúng trong nó, có rất nhiều cách. Nhưng đơn giản nhất trong số đó là tìm kiếm nhị phân. Phương pháp là gì? Và làm thế nào để thực hiện một tìm kiếm nhị phân? Pascal là môi trường đơn giản nhất để tổ chức một chương trình như vậy, vì vậy chúng tôi sẽ sử dụng nó để nghiên cứu.

Thứ nhất, chúng tôi sẽ phân tích những lợi ích của phương pháp này, sau khi tất cả, vì vậy chúng tôi có thể hiểu, Điểm trong nghiên cứu chủ đề này là gì. Vì vậy, giả sử có một mảng có kích thước ít nhất 100000000 phần tử, trong đó bạn cần phải tìm một phần tử cụ thể. Tất nhiên, vấn đề này có thể dễ dàng được giải quyết bằng một tìm kiếm tuyến tính đơn giản, trong đó chúng ta sử dụng một vòng lặp để so sánh các phần tử mong muốn với tất cả những gì tồn tại trong mảng đó. Vấn đề là việc thực hiện ý tưởng này sẽ mất quá nhiều thời gian. Trong một chương trình Pascal đơn giản cho một số thủ tục và với ba dòng văn bản chính, bạn sẽ không nhận thấy nó, nhưng khi bạn bắt đầu các dự án lớn hoặc nhỏ với nhiều nhánh và chức năng tốt, chương trình hoàn thành sẽ được nạp quá lâu. Đặc biệt là nếu máy tính có hiệu suất kém. Vì vậy, có một tìm kiếm nhị phân, làm giảm thời gian tìm kiếm ít nhất là hai lần.

Vì vậy, nguyên tắc của phương pháp này là gì? Ngay lập tức nó là đáng giá để nói rằng tìm kiếm nhị phân không có trong bất kỳ mảng, nhưng chỉ trong một tập hợp các số. Tại mỗi bước tiếp theo, phần tử trung bình của mảng được lấy (tham chiếu đến số nguyên tố). Nếu số mong muốn lớn hơn mức trung bình, thì mọi thứ ở bên trái, có nghĩa là, ít hơn phần tử trung bình, có thể bị loại bỏ và không được tìm kiếm ở đó. Ngược lại, nếu ít hơn trung bình, trong số các con số ở bên phải, bạn không thể tìm kiếm chúng. Tiếp theo, chúng ta sẽ chọn một vùng tìm kiếm mới, trong đó phần tử đầu tiên sẽ là phần tử trung gian của toàn bộ mảng và phần tử cuối cùng sẽ là phần tử cuối cùng. Số trung bình của khu vực mới sẽ là ¼ của toàn bộ phân đoạn, đó là (phần tử cuối cùng + yếu tố trung bình của toàn bộ mảng) / 2. Một lần nữa, cùng một hoạt động được thực hiện - so sánh với số trung bình của mảng. Nếu giá trị mong muốn thấp hơn mức trung bình, hãy loại bỏ phía bên phải và làm tương tự cho đến khi tìm thấy phần tử trung gian.

Tất nhiên, cách tốt nhất để xem ví dụ là làm thế nào để viết một tìm kiếm nhị phân. Pascal ở đây phù hợp với bất cứ ai - phiên bản không quan trọng. Hãy viết một chương trình đơn giản.

Nó sẽ có một mảng từ 1 đến h tên là "massiv", một biến thể biểu thị một ranh giới tìm kiếm thấp hơn, được gọi là "niz", một giới hạn trên có tên là "verh", phần tử tìm kiếm ở giữa là "sredn"; Và số yêu cầu là "isk".

Vì vậy, trước tiên gán các giới hạn trên và dưới của khoảng tìm kiếm:

Niz: = 1;
Verh: = h + 1;

Sau đó chúng tôi tổ chức chu kỳ "trong khi đáy là thấp hơn giới hạn trên":

Trong khi niz Bắt đầu

Tại mỗi bước, chia đoạn cho 2:

Sredn: = (niz + verh) div 2; {Sử dụng hàm div vì chúng ta chia phần còn lại}

Mỗi lần chúng tôi tiến hành séc. Nếu trung bình bằng với mong muốn, chúng ta sẽ ngắt chu trình, vì phần tử mong muốn đã được tìm thấy:

Іf sredn = isk sau đó phá vỡ;

Nếu phần tử trung gian của mảng lớn hơn mảng mà chúng ta đang tìm kiếm, chúng ta loại bỏ phía bên trái, tức là chúng ta gán phần tử trung gian cho ranh giới phía trên:

Nếu massiv [sredn]> isk sau đó verh: = sredn;

Và nếu ngược lại, thì chúng ta làm cho giới hạn dưới:

Else niz: = sredn;
Kết thúc;

Đó là tất cả những gì sẽ có trong chương trình.

Hãy phân tích cách thức phương pháp nhị phân sẽ xem xét trong thực tế. Lấy một mảng như vậy: 1, 3, 5, 7, 10, 12, 18 và tìm số 12 trong đó.

Tổng cộng, chúng ta có 7 yếu tố, vì vậy trung bình sẽ là thứ tư, giá trị của nó là 7.

Từ 12 đến lớn hơn 7, các phần tử 1,3 và 5 có thể bị loại bỏ. Tiếp theo, chúng ta có 4 số còn lại, 4/2 mà không có phần còn lại là 2. Vì vậy, phần tử trung gian mới sẽ là 10.

Kể từ 12 là hơn 10, chúng tôi loại bỏ 7. Chỉ có 10, 12 và 18 là trái.

Ở đây yếu tố giữa đã là 12, đây là số yêu cầu. Nhiệm vụ đã hoàn thành - số 12 được tìm thấy.