Tìm kiếm nhị phân (chặt nhị phân) toàn tập

Đã lâu rồi mình chưa viết bài mới, hôm nay mình xin chia sẻ với các bạn cách code thuật toán tìm kiếm phân mà mình thường sử dụng.

Chắc mọi người cũng biết, cùng một thuật toán tìm kiếm nhị phân nhưng có rất nhiều cách code khác nhau, tất cả đều chính xác, tốc độ nhanh như nhau. Và cách mình chia sẻ dưới đây là một trong những cách dễ hiểu nhất, linh hoạt nhất mà tốc độ chạy cũng khá tốt (cách này của anh Kiên – HCB Olympic Tin học Quốc tế)

Dãy con tăng – Tìm phần tử lớn nhất nhỏ hơn x (chỉ số lớn nhất)

// day con tang – tim phan tu lon nhat nho hon x ( chi so lon nhat);

function tim2(r,x : longint) : longint;

  var d,c,g : longint;

  begin

    d:=0;c:=r;

    g:=(d+c) div 2;

    while (g<>d) and (g<>c) do

      begin

        if b[g]>=x then c:=g else d:=g;

        g:=(d+c) div 2;

      end;

    for g:=c downto  d do

      if b[g]<x then exit(g);

   end;

Dãy con tăng – Tìm số bé nhất lớn hơn hoặc bằng x (chỉ số bé nhất)

// day con tang – so be nhat lon hon hoac bang x (chi so be nhat);

sort(a);

left=1, right=n;
i = (left + right) / 2;

while (left != i) and (i != right) do
    if a[i]>=k then right = i;
    else left = i;
    i = (left + right) / 2;

for i = left to right do

if a[i]>=k then return a[i];

print “Not found”

Dãy con tăng – Tìm số bé nhất lớn hơn hoặc bằng x (chỉ số lớn nhất)

// day con tang – so be nhat lon hon hoac bang x ( chi so lon nhat);

sort(a);

left=1, right=n;
i = (left + right) / 2;

while (left != i) and (i != right) do
    if a[i]>k then right = i;
    else left = i;
    i = (left + right) / 2;

for i = right to left do

if a[i]<=k then return a[i];

print “Not found”

Dãy con giảm – Tìm phần tử cuối cùng lớn hơn x

//day con giam – tim phan tu cuoi cung lon hon x

function tim1(r,x : longint) : longint;

  var d,c,g : longint;

  begin

    d:=0;c:=r;

    g:=(d+c) div 2;

    while (g<>d) and (g<>c) do

      begin

        if b[g]>x then d:=g else c:=g;

        g:=(d+c) div 2;

      end;

    for g:=c downto d do

      if b[g]>x then exit(g);

  end;

Dãy con giảm – Tìm phẩn tử đầu tiên nhỏ hơn x

//day con giam – tim phan tu dau tien nho hon x

function tim1(r,x : longint) : longint;

  var d,c,g : longint;

  begin

    d:=0;c:=r;

    g:=(d+c) div 2;

    while (g<>d) and (g<>c) do

      begin

        if b[g]>x then d:=g else c:=g;

        g:=(d+c) div 2;

      end;

    for g:=d to c do

      if b[g]>x then exit(g);

  end;

Các bài khác nhau với các yêu cầu tìm kiếm khác nhau bạn có thể dễ dàng sửa đổi cho phù hợp nếu sử dụng cách tìm kiếm nhị phân mình vừa trình bày.

Mọi thắc mắc rất mong nhận được từ quý bạn đọc <3

Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*