Thuật toán tìm kiếm nhị phân

Nguồn: Topcoder

Người dịch:

Bạn đang xem: thuật toán tìm kiếm nhị phân

Nguyễn Nhật Minh Khôi - VNU University of Science. Biên biên soạn lại kể từ bạn dạng dịch của Vũ Thị Thiên Anh

Reviewer: Hoàng Xuân Nhật, Trần Quang Lộc

Tìm tìm hiểu nhị phân (hay thường hay gọi là chặt nhị phân) là một trong những vô số những thuật toán cơ bạn dạng của khoa học tập PC. Trong nội dung bài viết này, tất cả chúng ta sẽ xây dựng dựng một nền tảng lý thuyết, tiếp sau đó thể hiện cơ hội thiết lập thuật toán này một cơ hội chuẩn chỉnh xác.

Bài toán cởi đầu: Tìm độ quý hiếm mang đến trước vô một sản phẩm tiếp tục chuẩn bị xếp

Mở đầu, tao sẽ tới với việc dùng tìm hiểu tìm tòi nhị phân đơn giản và giản dị nhất. Đề bài bác như sau:

Cho trước một sản phẩm $A$ được chuẩn bị tăng dần, trả về địa điểm của thành phần có mức giá trị $x$ vô $A$. Lưu ý: nhằm đơn giản và giản dị, tao fake sử những thành phần vô mảng $A$ có mức giá trị phân biệt.

Ví dụ

Đầu tiên, tao tiếp tục xét một ví dụ giúp xem được tư tưởng của thuật toán. Cho $A = [0, 5, 13, 19, 2, 41, 55, 68, 72, 81, 98]$ và $x = 55$, thuật toán tiếp tục ra mắt như hình dưới:

Ở lượt tìm hiểu trước tiên, không khí tìm hiểu tìm tòi là tụ họp $S = {1,\ldots,11}$ bao gồm toàn bộ những chỉ số của mảng. Bắt đầu với việc lựa chọn thành phần trung vị của không khí tìm hiểu tìm tòi lúc này (chính là $6$), tao đánh giá $A[6]=41 < 55 = x$. Do theo đòi đề bài bác mảng $A$ được bố trí tăng dần dần, tao hiểu rằng toàn bộ những thành phần với chỉ số $1,\ldots,6$ đều nhỏ rộng lớn độ quý hiếm cần thiết tìm hiểu $x$. Do tê liệt, bọn chúng chắc chắn ko thể là kết quả, khi tê liệt không khí tìm hiểu tìm tòi rất có thể thu hẹp lại $S = {7,\ldots,11}$, tức giảm lên đường 50%.

Tương tự động, ở lượt tìm hiểu loại nhị, tao xét thành phần trung vị của không khí tìm hiểu tìm tòi lúc này (chính là $9$), nhận ra $A[9]=72 > 55 = x$. Cũng vì thế mảng $A$ được bố trí tăng dần dần, tao hiểu rằng toàn bộ những thành phần nằm tại kể từ $9,\ldots,11$ đều to hơn độ quý hiếm cần thiết tìm hiểu $x$. Do tê liệt, bọn chúng chắc hẳn rằng ko thể là thành quả, khi tê liệt không khí tìm hiểu tìm tòi tiếp tục lại sụt giảm 50% $S = {7,\ldots,8}$.

Ở lượt tìm hiểu sau cuối, tao cũng xét thành phần trung vị của không khí tìm hiểu tìm tòi lúc này ở địa điểm $7$ (ở phía trên con số thành phần của không khí tìm hiểu tìm tòi là chẵn, vì thế với nhị thành phần trung vị, tao rất có thể lựa chọn 1 trong nhị đều được, ở ví dụ này tao lựa chọn thành phần trung vị đầu tiên), Nhận thấy $A[7] = 55 = x$, tao Tóm lại $5$ đó là địa điểm của thành phần cần thiết tìm hiểu và giới hạn thuật toán.

Tổng quát lác hóa bài bác toán

Từ ví dụ bên trên, tao rất có thể đơn giản và dễ dàng nắm được phát minh của thuật toán tìm kiếm nhị phân. Đúng như tên thường gọi, thuật toán tiếp tục liên tiếp phân chia không khí tìm hiểu tìm tòi trở thành nhị nửa và loại 50% lên đường. Thuật toán rất có thể trình diễn như sau:

Ta giữ lại một không khí tìm hiểu tìm tòi $S$ là một trong những sản phẩm con cái những độ quý hiếm rất có thể là thành quả (ở đó là chỉ số những thành phần vô $A$). Ban đầu, không khí tìm hiểu tìm tòi là toàn cỗ những chỉ số của mảng $S={1,\ldots,n}$ với $n$ là chỉ số thành phần sau cuối của $A$.
Ở từng bước, thuật toán đối chiếu độ quý hiếm cần thiết tìm hiểu với thành phần với chỉ số là trung vị vô không khí tìm hiểu tìm hiểu. Dựa bên trên sự đối chiếu tê liệt, thêm vào đó việc tao biết sản phẩm $A$ với trật tự, tao rất có thể loại 50% số thành phần của $S$. Lặp lên đường tái diễn quy trình này, sau cuối tao sẽ tiến hành một không khí tìm hiểu tìm tòi bao hàm một thành phần độc nhất.
Khi tê liệt, nếu như thành phần độc nhất tê liệt vày với độ quý hiếm cần thiết tìm hiểu $x$ thì này đó là nghiệm của việc, nếu như không thì việc vô nghiệm.

Ở phía trên với nhị chú ý khi thiết lập thuật toán:

Do không khí tìm hiểu tìm tòi vẫn là một đoạn liên tiếp những độ quý hiếm nguyên vẹn, tao ko cần thiết lưu toàn bộ thành phần của không khí khi tìm hiểu tìm tòi tuy nhiên chỉ việc giữ lại nhị biến chuyển low và high biểu tượng mang đến thành phần đầu và cuối của đoạn.
Ta rất có thể tối ưu thuật toán rộng lớn bằng sự việc dừng sớm nếu như vô quy trình đối chiếu gặp gỡ một thành phần trung vị thỏa đòi hỏi đề bài bác chứ không cần cần thiết đợi cho tới khi không khí tìm hiểu tìm tòi chỉ từ một thành phần.

Dưới đó là code minh họa viết lách vày ngôn từ C++. Trong tình huống độ quý hiếm cần thiết tìm hiểu ko tồn bên trên trong tầm tìm hiểu tìm tòi thì thuật toán tiếp tục trả về $-1$

int binary_search(int A[], int sizeA, int target) {
    int lo = 1, hi = sizeA;
    while (lo <= hi) {
        int mid = lo + (hi - lo)/2;
        if (A[mid] == target)
            return mid;       	
        else if (A[mid] < target)
            lo = mid+1;
        else
            hi = mid-1;
    }
    // không tìm kiếm thấy độ quý hiếm target vô mảng A
    return -1;
}

Độ phức tạp thuật toán

Ở từng bước, độ dài rộng không khí tìm hiểu tìm tòi bị sụt giảm 50%. Ta thường thấy rằng chừng phức tạp của thuật toán là $O(\log(N))$ với $N$ là số thành phần lúc đầu của không khí tìm hiểu tìm hiểu.

Hàm $\log$ là một trong những hàm tăng vô cùng chậm chạp. Ví dụ như nếu như cần tìm hiểu tìm tòi độ quý hiếm trong một triệu thành phần, với tìm hiểu tìm tòi nhị phân chỉ việc tối nhiều là 21 bước.

Tìm tìm hiểu nhị phân vô tủ sách chuẩn chỉnh STL

C++ Standard Template Library tiếp tục thiết lập sẵn tìm hiểu tìm tòi nhị phân vày những hàm lower_bound, upper_bound, binary_search, equal_range, độc giả rất có thể xem thêm tùy nằm trong vô mục tiêu dùng.

Tìm tìm hiểu nhị phân tổng quát

Ở phần trước, tao tiếp tục xét dạng đơn giản và giản dị nhất của tìm hiểu tìm tòi nhị phân. Trong phần này, tất cả chúng ta tiếp tục tổng quát lác hóa thuật tìm hiểu tìm tòi nhị phân cho 1 lớp việc rộng lớn rộng lớn. Ta tiếp tục thấy tìm hiểu tìm tòi nhị phân rất có thể không ngừng mở rộng nhằm vận dụng mang đến bất kỳ loại hàm số đơn điệu này nhận thông số nguồn vào là số nguyên. Nói một cơ hội đơn giản và giản dị, một hàm số đơn điệu là một hàm tăng hoặc một hàm giảm. Trong ví dụ đầu bài bác, rõ ràng mảng bố trí tăng rất có thể coi như 1 "hàm tăng".

Cơ sở lý thuyết: Định lý chủ yếu của tìm hiểu tìm tòi nhị phân

Khi gặp gỡ một việc tuy nhiên tao đoán được rất có thể sử dụng tìm hiểu tìm tòi nhị phân nhằm giải, thì tao cần minh chứng tính đích thị đắn suy đoán của tất cả chúng ta. Do tê liệt, thi công một hạ tầng lý thuyết vững chãi là vô nằm trong quan trọng. Sau phía trên, tôi tiếp tục trình diễn một tấm tổng quát lác hóa nữa cho những việc rất có thể vận dụng tìm hiểu tìm tòi nhị phân, tuy nhiên song này đó là ví dụ thực tiễn với việc mở màn.

Cho không khí tìm hiểu tìm tòi $S$ bao hàm những ứng viên mang đến thành quả của việc. Ta khái niệm môt hàm đánh giá $P: S \rightarrow {\texttt{true}, \texttt{false}}$ là hàm nhận một ứng viên $x \in S$ và trả về độ quý hiếm $\texttt{true}/\texttt{false}$ cho thấy thêm $x$ với hợp thức hay là không (tùy vô việc tuy nhiên khái niệm hợp thức tiếp tục không giống nhau). Hiểu đơn giản và giản dị, hàm $P$ là hàm "kiểm tra" một đặc thù này tê liệt, coi một ứng viên mang đến thành quả của việc với thỏa đặc thù tê liệt ko.

Với ví dụ ở đầu bài bác, thay cho tìm hiểu chỉ số của thành phần có mức giá trị $55$, tao rất có thể viết lách lại đề bài bác trở thành "tìm chỉ số nhỏ nhất sao mang đến thành phần ở chỉ số tê liệt to hơn hoặc vày $55$". Khi tê liệt, không khí tìm hiểu tìm tòi lúc đầu $S = {1,\ldots,11}$ (ban đầu từng chỉ số của mảng đều rất có thể là kết quả) và $P(x) = boolean(a[x] \geq 55)$ trả về $\texttt{true}$ nếu như $a[x] \geq 55$ và $\texttt{false}$ nếu như $a[x] < 55$.

Định lý chính (Main Theorem) cho thấy thêm rằng: một việc chỉ rất có thể vận dụng tìm hiểu tìm tòi nhị phân nếu như và chỉ nếu như hàm đánh giá $P$ của việc thỏa mãn \begin{equation} \forall x, nó \in S, nó > x \wedge P(x) = \texttt{true} \Rightarrow P(y) = \texttt{true} \tag{*} \label{eq:1} \end{equation}

Lưu ý rằng đặc thù bên trên của hàm đánh giá $P$ cũng tương tự với đặc thù sau: \begin{equation} \forall x, nó \in S, nó < x \wedge P(x) = \texttt{false} \Rightarrow P(y) = \texttt{false} \tag{**} \label{eq:2} \end{equation}

Sự tương tự ở phía trên rất có thể minh chứng vày cách thức phản hội chứng, nhằm tách nội dung bài viết quá dông dài, phần minh chứng nhằm lại cho chính mình gọi.

Định lý chủ yếu đem mang đến tất cả chúng ta một vấn đề vô cùng cần thiết, này đó là điều khiếu nại cần thiết và đầy đủ nhằm một việc rất có thể giải vày tìm hiểu tìm tòi nhị phân. Để nắm được vì sao, tất cả chúng ta hãy phân tách kĩ rộng lớn chân thành và ý nghĩa đặc thù của hàm $P$ tuy nhiên tấp tểnh lý yêu thương cầu

Tính hóa học $\eqref{eq:1}$ rất có thể lý giải như sau: nếu $x$ hợp thức thì từng thành phần $y > x$ đều phù hợp lệ. Tính hóa học này chung tất cả chúng ta loại lên đường nửa sau của không khí tìm hiểu tìm tòi vì thế tiếp tục biết chắc chắn $x$ là thành phần nhỏ nhất vô nửa sau hợp thức, tao ghi nhận $x$ là thành quả trong thời điểm tạm thời và nối tiếp tìm hiểu coi với thành phần này ở nửa đầu (nhỏ rộng lớn $x$) hợp thức hay là không.
Tương tự động, đặc thù $\eqref{eq:2}$ rất có thể lý giải như sau: nếu $x$ ko hợp thức thì từng thành phần $y < x$ đều không phù hợp lệ. Tính hóa học này chung tất cả chúng ta loại lên đường nửa trước của không khí tìm hiểu tìm tòi vì thế tiếp tục biết chắc chắn bọn chúng ko hợp thức, tao chỉ quan hoài những thành phần ở nửa sau (lớn rộng lớn $x$) tuy nhiên tao không biết vấn đề bọn chúng với hợp thức hay là không.

Nếu tao tính độ quý hiếm $P(x)$ mang đến từng thành phần vô $S$ lúc đầu, tao sẽ tiến hành một sản phẩm liên tục những độ quý hiếm $\texttt{false}$ ngay lập tức kề một sản phẩm liên tục những độ quý hiếm $\texttt{true}$ (từ ni gọi là sản phẩm $P(S)$). Dễ thấy tao rất có thể vận dụng tìm hiểu tìm tòi nhị phân bên trên sản phẩm $P(S)$ mới mẻ này nhằm tìm hiểu độ quý hiếm $x$ nhỏ nhất vừa lòng $P(x) = \texttt{true}$ (hoặc cũng rất có thể thực hiện cơ hội tìm hiểu độ quý hiếm $x$ lớn nhất tuy nhiên $P(x) = \texttt{false}$, tuy vậy ở phía trên tao ko chọn lựa cách này).

Với ví dụ đầu bài bác, như tiếp tục trình bày $P(x) = boolean(A[x] \geq 55)$. Dễ thấy $P$ vừa lòng đặc thù trước tiên, vì thế $A$ được chuẩn bị tăng dần dần nên nếu như $A[x] \geq 55$ thì chắc hẳn rằng những thành phần $y$ sau $x$ đều thỏa $A[y] \geq A[x] \geq 55$. Tương tự động tao cũng suy rời khỏi được, nếu như $A[x] < 55$ thì chắc hẳn rằng những thành phần $y$ trước $x$ đều thỏa $A[y] \leq A[x] < 55$. Áp dụng hàm $P(x) = boolean(A[x] \geq 55)$ mang đến từng thành phần của $S={1,\ldots,11}$ tao với hình sau

Chú ý rằng tao thấy rất có thể đơn giản và dễ dàng thi công tấp tểnh lý chủ yếu dựa vào một hàm đánh giá $P$ ngược lại, tức $P(S)$ tiếp tục là một trong những sản phẩm $\texttt{true}$ liên tục theo đòi sau vày $\texttt{false}$ liên tục. Tuy nhiên, ở phía trên tao tiếp tục chỉ xét một tình huống nhằm nội dung bài viết cụt gọn gàng rộng lớn, tình huống sót lại rất có thể thực hiện tương tự động.

Từ tấp tểnh lý bên trên, tao rút rời khỏi được then chốt nhằm giải một việc sử dụng tìm hiểu tìm tòi nhị phân là tao cần thiết thiết kế tiếp được hàm $P$ phải chăng sao mang đến vừa lòng ĐK vô tấp tểnh lý chính.

Xem thêm: tính chất của cuộc khởi nghĩa yên thế

Cuối nằm trong, vì sao tao cần tốn sức tổng quát lác hóa thuật toán này thay cho sử dụng thủ tục đơn giản và giản dị ở ví dụ đầu? Đó là vì thế nhiều việc ko thể ở bên dưới dạng tìm hiểu tìm tòi một độ quý hiếm rõ ràng, tuy nhiên tao lại rất có thể khái niệm một hàm đánh giá thỏa đòi hỏi tấp tểnh lý chủ yếu nhằm rất có thể vận dụng tìm hiểu tìm tòi nhị phân. phẳng cơ hội tê liệt, tao rất có thể không ngừng mở rộng lớp việc rất có thể giải vày tìm hiểu tìm tòi nhị phân.

Ví dụ điển hình nổi bật mang đến việc vận dụng tấp tểnh lý là với việc Tìm căn bậc hai, thay cho chất vấn "Số $x$ này bình phương lên thì vày $a$?" và tìm hiểu tìm tòi tuần tự động toàn bộ những tình huống, tao rất có thể khái niệm hàm $P(x)$ vấn đáp mang đến thắc mắc "$x^2$ với to hơn hoặc vày $a$ hoặc không?" tiếp sau đó sử dụng tìm hiểu tìm tòi nhị phân nhằm tìm hiểu $x$ nhỏ nhất vừa lòng. Với thủ tục này tao rất có thể đơn giản và giản dị hóa việc trở thành một việc yes/no, chưa dừng lại ở đó còn hạn chế chừng phức tạp của việc kể từ $O(n)$ xuống chỉ từ $O(\log(n))$.

Cài bịa đặt thuật toán tổng quát

Trước khi thiết lập thuật toán, tao cần vấn đáp những thắc mắc sau:

Dãy $P(S)$ của công ty với dạng $\texttt{false}-\texttt{true}$ ($\texttt{false}$ liên tục rồi $\texttt{true}$ liên tiếp) hoặc $\texttt{true}-\texttt{false}$ (ngược lại)? Tại thiết lập phía bên dưới tiếp tục mặc tấp tểnh sản phẩm $P(S)$ với dạng $\texttt{false}-\texttt{true}$, nên là nếu như sản phẩm $P(S)$ của công ty với dạng $\texttt{true}-\texttt{false}$, hãy hòn đảo hàm $P(x)$ của công ty ngược lại.
Bài của công ty với luôn luôn với nghiệm không? Nếu ko hãy đánh giá trước lúc tìm hiểu tìm tòi nhị phân nhằm tiết kiệm chi phí ngân sách đo lường.
Mục chi của công ty là tìm hiểu thành phần $\texttt{false}$ lớn số 1 hoặc tìm hiểu thành phần $\texttt{true}$ nhỏ nhất? Tại phía trên tiếp tục trình diễn cả nhị cơ hội.
Nếu việc với nghiệm, hãy đáp ứng độ quý hiếm ngăn bên dưới và ngăn bên trên của khoảng tầm tìm hiểu tìm tòi (biến lo và hi) là chính thức và kết cổ động của một khoảng đóng góp tuy nhiên chắc hẳn rằng chứa chấp thành quả cần thiết tìm (phần tử $x$ trước tiên tuy nhiên $P(x) = \texttt{true}$). Hãy đáp ứng ĐK này trong khi thu hẹp không khí tìm hiểu tìm tòi nhằm tách xẩy ra lỗi.
Phạm vi tìm hiểu tìm tòi tiếp tục đầy đủ rộng lớn chưa? Sẽ có khá nhiều khi chấm hoàn thành các bạn nhìn thấy là bản thân thiếu hụt vài ba tình huống biên. Vì thời hạn chạy chỉ tăng theo đòi hàm logarit $O(\log(N))$, các bạn trọn vẹn rất có thể nâng rộng lớn khoảng tầm tìm hiểu tìm tòi rời khỏi tuy nhiên hiếm khi lo ngại bị quá thời hạn. Tuy nhiên, cần nhằm ý những lỗi như tràn mảng, tràn số,…
Luôn đánh giá tình huống $P(S) = [\texttt{false},\texttt{true}]$. Để hiểu nguyên nhân vì sao hãy tham khảo Trường phù hợp 2 của thiết lập.

TH1: tìm hiểu $x$ nhỏ nhất tuy nhiên $P(x) = \texttt{true}$. Dưới đó là đoạn code kiểu viết lách vày C++.

bool P(int x) {
    // Logic của hàm Phường ở đây
    return true;  // thay cho độ quý hiếm này vày độ quý hiếm đích thị logic.
}

int binary_search(int lo, int hi) {
    while (lo < hi) {
        int mid = lo + (hi-lo)/2;
        if (P(mid) == true)
            hi = mid;
        else
            lo = mid+1;
    }
  	
    if (P(lo) == false)
        return -1; // P(x) = false với từng x nằm trong S, việc vô nghiệm.
  	
   return lo; // lo ngại là độ quý hiếm x nhỏ nhất tuy nhiên P(x) = true
}

Hai loại cần thiết là $hi = mid$ và $lo = mid+1$, bọn chúng đỡ đần ta thu hẹp không khí tìm hiểu tìm tòi dần dần.

Khi $P(mid) = \texttt{true}$, tao rất có thể vứt nửa sau của không khí tìm hiểu tìm tòi vì thế tiếp tục biết thành phần vô tê liệt luôn luôn hợp thức. Tuy nhiên tao vẫn cần lưu giữ $mid$ vô không khí tìm hiểu tìm tòi mới mẻ vì thế nó rất có thể là thành phần trước tiên tuy nhiên $P = \texttt{true}$. Do tê liệt không khí tìm hiểu tìm tòi mới mẻ được xem là $S={lo, mid}$, tao gán $hi = mid$.

Tương tự động, khi $P(mid) = \texttt{false}$, tao rất có thể vứt nửa đầu (bao bao gồm cả thành phần $mid$) vì thế toàn bộ những thành phần này đều ko hợp thức. Lúc này không khí tìm hiểu tìm tòi mới mẻ được xem là $S={mid + 1, hi}$, tao gán $lo = mid+1$.

TH2: tìm hiểu $x$ lớn số 1 tuy nhiên $P(x) = \texttt{false}$, suy đoán tương tự động như bên trên, tao với đoạn code như sau:

bool P(int x) {
    // Logic của hàm Phường ở đây
    return true;  // thay cho độ quý hiếm này vày độ quý hiếm đích thị logic.
}

int binary_search(int lo, int hi) {
    while (lo < hi) {
        int mid = lo + (hi-lo+1)/2;
        if (P(mid) == true)
            hi = mid - 1;
        else
            lo = mid;
    }
  	
    if (P(lo) == true)
        return -1; // P(x) = true với từng x nằm trong S, việc vô nghiệm.
  	
   return lo; // lo ngại là độ quý hiếm x lớn số 1 tuy nhiên P(x) = false
}

Bạn tiếp tục vướng mắc rằng vì sao phương pháp tính $mid$ lại sở hữu một tí khác lạ đối với thuật toán trước tiên. Để nắm được vì sao tao cần thực hiện thế, tao tiếp tục xét tình huống sau: vô quy trình tìm hiểu tìm hiểu, nếu như bên trên 1 thời diểm này này mà sản phẩm $P(S)$ tạo nên vày những thành phần của không khí tìm hiểu tìm tòi với dạng như sau

Nếu tao tính $mid = lo ngại + (hi-lo)/2$, đoạn code tiếp tục lặp vô hạn. Nó tiếp tục luôn luôn lựa chọn thành phần trung vị là $mid = lo$, tuy nhiên cận bên dưới $lo$ sẽ không còn dịch rời vì thế nó mong muốn níu lại thành phần với $p = \texttt{false}$ thỏa đòi hỏi tìm hiểu tìm tòi tê liệt. Do tê liệt, tao thay cho thay đổi công thức tính $mid$ trở thành $mid = lo ngại + (hi-lo+1)/2$, thực hiện vì vậy tiếp tục khiến cho cận bên dưới sẽ tiến hành thực hiện tròn trặn lên thay cho thực hiện tròn trặn xuống, khi tê liệt nó rất có thể vô hiệu hóa thành phần $\texttt{true}$ trước lúc xét thành phần $\texttt{false}$. Có vô số cách thức thực hiện không giống nhằm tiến hành điều này, tuy vậy, đó là cơ hội dễ nắm bắt nhất. Do vậy, hãy luôn luôn trực tiếp đánh giá demo tình huống $P(S) = [\texttt{false}, \texttt{true}]$.

Một điều rất có thể các bạn đang được vướng mắc nữa là vì sao nhằm tìm hiểu trung vị tao tính $mid = lo ngại + (hi-lo)/2$ chứ không cần cần $mid = (hi+lo)/2$. Sở dĩ cần thực hiện vì vậy là nhằm tách kĩ năng xẩy ra lỗi thực hiện tròn trặn số nguyên vẹn, tao mong muốn phép tắc phân chia được sản xuất tròn trặn xuống, về ngay sát với cận bên dưới, tuy vậy phép tắc chia thành tròn trặn không giống khi với số âm, nên nếu như $(lo+hi)$ là số âm thì thành quả có khả năng sẽ bị thực hiện tròn trặn lên. Code như vô kiểu tê liệt chung quy trình đo lường đều được sản xuất tròn trặn phù hợp logic. Đối với những việc tuy nhiên chỉ việc xử lý độ quý hiếm dương thì lỗi này sẽ không xẩy ra.

Cài bịa đặt thuật toán với nửa khoảng

Cài bịa đặt với đoạn đóng góp $[lo, hi]$ như bên trên với điểm mạnh là dễ nắm bắt. Tuy nhiên, trở lại một ít với hạ tầng lý thuyết: với sản phẩm $P(S)$ với dạng $\texttt{false}-\texttt{true}$, thực tiễn tao nên lựa chọn độ quý hiếm $lo$ và $hi$ tuy nhiên $P(lo) = \texttt{false}$ và $P(hi) = \texttt{true}$ nhằm đáp ứng luôn luôn tìm kiếm ra nghiệm. Do tê liệt sẽ không còn ổn định nếu mà sản phẩm $P(S)$ của tao đều toàn độ quý hiếm $\texttt{false}$ (tức vô nghiệm). Trong tình huống này, thiết lập với đoạn đóng góp đạt thêm đoạn đánh giá nhằm return - 1.

Giải pháp mang đến tình huống này đó là cài bịa đặt với nửa khoảng. Để ý rằng vô tình huống vô nghiệm, cơ hội thiết lập với mức đóng góp tiếp tục trả về cận bên trên $hi$ của đoạn tìm hiểu tìm tòi ban đầu (do chỉ mất cận bên dưới $lo$ liên tiếp dịch gửi lên và tiếp xúc với $hi$). Hơn nữa, thuật toán của tao ko khi nào gọi $P(hi)$ vì thế để sở hữu $mid = hi$, tao sẽ rất cần với $lo = hi$, tuy nhiên khi tê liệt thuật toán chắc hẳn rằng tiếp tục giới hạn vì thế ĐK while (lo < hi) vô thiết lập.

Điều này mang đến tao một ý tưởng: tạo nên một độ quý hiếm $hi' = hi + 1$ ảo và đem tấp tểnh coi $P(hi') = \texttt{true}$. Ta tiếp tục tìm hiểu tìm tòi nhị phân bên trên đoạn $[lo, hi']$ mới mẻ và nếu như việc vô nghiệm thì Search Engine Results Page được xem là $hi'$, tao không rất cần được đánh giá nhằm return -1. Sở dĩ gọi là thiết lập với nửa khoảng tầm vì thế khi truyền thông số mang đến hàm là $lo$ và $hi$, thực rời khỏi tao chỉ mong muốn thành quả vô nửa khoảng tầm $[lo, hi)$, còn $hi$ đơn giản độ quý hiếm ảo cho thấy thêm tình huống vô nghiệm.

Cài bịa đặt cũng tương tự động với đoạn đóng góp, nước ngoài trừ việc tao vô hiệu hóa lên đường đoạn code đánh giá vô nghiệm:

bool P(int x) {
    // Logic của hàm Phường ở đây
    return true;  // thay cho độ quý hiếm này vày độ quý hiếm đích thị logic.
}

// ghi nhớ rằng tao cần truyền hi to hơn một đơn vị chức năng 
// đối với đoạn tìm hiểu tìm tòi thực sự
int binary_search(int lo, int hi) {
    while (lo < hi) {
        int mid = lo + (hi-lo)/2;
        if (P(mid) == true)
            hi = mid;
        else
            lo = mid+1;
    }
  	
   return lo; // lo ngại là độ quý hiếm x nhỏ nhất tuy nhiên P(x) = true
}

Cách thiết lập này còn tồn tại một điểm mạnh không giống, này đó là vô C++ và thật nhiều ngôn từ xây dựng không giống thì mảng chính thức kể từ $0$, nên là nếu như cần thiết tìm hiểu một thành phần này tê liệt vô mảng thì với thiết lập vày nửa khoảng tầm thông số truyền vô tiếp tục vô cùng rất đẹp, này đó là binary_search(0, N) với $N$ là số thành phần của mảng. Toàn cỗ tủ sách STL, lower_bound, upper_bound đều nhận nửa khoảng tầm, và thực tiễn nguyên tắc của những hàm này cũng như trên: không tìm kiếm rời khỏi đáp án thì trả về iterator end.

Lưu ý: Với tình huống tao mong muốn tìm hiểu địa điểm thành phần $\texttt{false}$ sau cuối thì nửa khoảng tầm cần thiết tìm hiểu được xem là (lo, hi] và hàm tiếp tục tự động hóa trả về lo nếu như từng độ quý hiếm trong tầm là $\texttt{true}$.

Ví dụ

Đến phía trên tao tiếp tục vận dụng những điều vừa vặn học tập vào trong 1 bài bác rõ ràng Leetcode 1011.

Trong bài bác này, một băng chuyền cần vận gửi những gói sản phẩm theo đòi trật tự mang đến trước vô $days$ ngày. Gói sản phẩm loại $i$ với trọng lượng $weights[i]$. lõi thường ngày băng chuyền chỉ rất có thể vận gửi tổng lượng tối nhiều là $MAX$. Đề bài bác đòi hỏi tìm hiểu $MAX$ nhỏ nhất nhằm băng chuyền rất có thể hoàn thành xong trọng trách được uỷ thác.

Để ý thấy rằng, với một trong những $MAX$, tao rất có thể đo lường được số ngày nhằm gửi không còn những gói sản phẩm sao cho từng ngày tổng lượng vận gửi không thật $MAX$. Ban đầu, uỷ thác gói sản phẩm $1$ nhằm ngày $1$ gửi. Nếu vận gửi gói sản phẩm $2$ trong thời gian ngày $1$ ko thực hiện tổng lượng trong thời gian ngày vượt lên trước $MAX$, thì tao tiếp tục gửi luôn luôn gói tê liệt trong thời gian ngày $1$. Nếu ko, tao tiếp tục gửi gói tê liệt trong thời gian ngày $2$. Làm theo lần lượt như vậy cho tới khi từng gói sản phẩm đều được gửi, tao sẽ sở hữu được được số ngày ít nhất cần thiết nhằm gửi không còn gói sản phẩm với tổng lượng thường ngày không thật $MAX$.

Quay lại đề bài bác, tao thấy rằng thực rời khỏi yếu tố của việc là tìm số $MAX$ nhỏ nhất sao mang đến số ngày ít nhất nhằm gửi không còn gói sản phẩm không thật $days$ ngày. Như vậy, tao rất có thể sử dụng tìm hiểu tìm tòi nhị phân với hàm đánh giá $P$ được thi công vày thuật toán tham lam lam được trình diễn phía trên nhằm đánh giá những độ quý hiếm $MAX$. Để ý đặc thù đơn điệu ở phía trên thể hiện nay ở trong phần nếu như $MAX$ tạo thêm thì con số ngày nhớ dùng chỉ rất có thể không thay đổi hoặc hạn chế đi nên hàm $P$ thỏa tấp tểnh lý chủ yếu và rất có thể vận dụng tìm hiểu tìm tòi nhị phân.

Sau đó là đoạn code kiểu vày C++:

// hàm đánh giá P
 bool check(int capacity, const vector<int>& weights, int days) {
    int current_weight = 0; --days;
    for(int i = 0; i < weights.size(); ++i) {
        if (current_weight + weights[i] <= capacity)
            current_weight += weights[i];
        else {
            --days;
            current_weight = weights[i];
        }
    }
    return days >= 0;
}

// hàm tìm hiểu tìm tòi nhị phân
int shipWithinDays(const vector<int>& weights, int days) {
    int lo = 0, hi = 0;
    for (int i = 0; i < weights.size(); ++i) {
        lo = max(lo, weights[i]);
        hi += weights[i];
    }

    while (lo < hi) {
        int mid = lo + (hi - lo)/2;
        if (check(mid, weights, days))
            hi = mid;
        else
            lo = mid + 1;
    }

    return lo;
}

Hàm tìm hiểu tìm tòi nhị phân đó là hàm shipWithinDays và hàm đánh giá là hàm check. Có một chú ý về sự việc lựa chọn cận bên dưới và cận bên trên. Cận bên trên rất có thể là bất kể số nguyên vẹn này đầy đủ rộng lớn, ở phía trên lựa chọn là tổng của toàn bộ những gói sản phẩm (cho tình huống tệ nhất cần thiết vận gửi vô đích thị một ngày). Tuy nhiên cận bên dưới cần vày tối thiểu là lượng của gói sản phẩm nặng nề nhất nhằm tách tình huống gói sản phẩm quá to nhằm gửi vô một ngày.

Để đánh giá thuật toán không xẩy ra lặp vô hạn với tình huống $[\texttt{false}, \texttt{true}]$, tao demo một test như sau: $weights = [1,1], days = 1$ và thấy thuật toán hoạt động và sinh hoạt chất lượng tốt.

Xem thêm: công thức tính cạnh huyền tam giác vuông

Độ phức tạp thuật toán là $O(n \cdot \log(SIZE))$ với $SIZE = hi -lo + 1$ là độ dài rộng của không khí tìm hiểu tìm tòi và $n$ là con số gói sản phẩm, vì thế thuật toán chạy vô cùng thời gian nhanh.

Tìm tìm hiểu nhị phân bên trên số thực

Tìm tìm hiểu nhị phân cũng rất có thể được vận dụng khi không khí tìm hiểu tìm tòi là một trong những đoạn số thực. Thông thường việc xử lý tiếp tục đơn giản và giản dị rộng lớn với số lý do tao ko cần bận tâm về sự việc dịch gửi cận:

bool P(double x) {
    // Logic của hàm Phường ở đây
    return true;  // thay cho độ quý hiếm này vày độ quý hiếm đích thị logic.
}

bool isTerminated(double lo, double hi) {
    // trả về thành quả của việc kiểm tra
    // lo ngại và hi với thỏa ĐK giới hạn ko 
}

double binary_search(double lo, double hi) {
    while (isTerminated(lo, hi) == false) {
        double mid = lo + (hi-lo)/2;
        if (P(mid) == true)
            hi = mid;
        else
            lo = mid;
    }
    // tầm nằm trong lo ngại và hi xấp xỉ 
    // ranh giới thân ái false và true
    return lo + (hi-lo)/2; 
}

Ta thông thường ko tìm kiếm ra độ quý hiếm tiềm năng một cơ hội đúng mực tuy nhiên chỉ rất có thể xấp xỉ thành quả, này đó là nguyên nhân với hàm ĐK giới hạn isTerminated. Thông thông thường với 2 cơ hội ra quyết định lúc nào giới hạn vòng lặp:

Dừng sau một trong những vòng lặp thắt chặt và cố định (fixed): thường thì khi thực hiện bài bác tập luyện bên trên TopCoder, chỉ việc lặp khoảng tầm 100 thứ tự là đầy đủ (nhiều là thừa) nhằm đạt được chừng đúng mực mong ước mang đến những bài bác dạng thế này.
Sai số vô cùng (absolute error): giới hạn khi $hi - lo ngại \leq \epsilon$ ($\epsilon$ thông thường vô cùng nhỏ, khoảng tầm $10^{-8}$). Cách này được dùng nếu như thời hạn chặt và các bạn cần tiết kiệm chi phí số thứ tự lặp.