Binary Search
Last updated
Last updated
Binary Search is an efficient algorithm for finding an item from a sorted set of items. Here is an example for finding -1 from the given list.
As the figure shows, adopting binary search can lower the time complexity from $O(N)$ to $O(\log N)$ [Note: When analysising Algorithms time and space complexity, $\log N$ stands for $log_2 N$]
The code pattern of binary search algorithms are easy to understand, we often use l, r, mid to point with the left and right pointer. mid is always calculated with the formular l + r // 2.
By extension, when solving a problem, we can also adopt binary search for searching the solution from a sorted list of possible solution. Here is an example, make your hands dirty.
For a better understanding, you can read the problem in CN Version.
The annual "stone jumping" competition is about to start again! The competition will be held in a straight river with huge rocks distributed in the river. The committee has selected two rocks as the starting and ending points of the competition. Between the start point and the end point, there are N pieces of rocks (the rocks that do not include the start point and the end point). During the competition, the players will start from the starting point and jump to the adjacent rocks at each step until they reach the finish line.
In order to increase the difficulty of the competition, the committee plans to remove some rocks to make the shortest jumping distance of the contestants as long as possible during the competition. Due to budget constraints, the committee can remove at most M rocks between the start and end points (the start and end rocks cannot be removed).
You should write a program to read L, N, M that represent the distance between starting point and ending point(L), the number of rocks between starting point and ending point(N), number of rocks the committe can remove at most(M). The data constraint is L >= 1, N >= M >= 0
For the following N lines, the i-th line has $D_i$, which represents the distance between the i-th rock and the starting point. The data constraint is (i < j) Di < Dj, Di != Dj
And your program should print an integer which is the maximum distance of minimum jumpping interval.
Sample I/O
Input Data:
Output Data:
Explanation:
After removing the rocks that distance from starting point are 2 and 14, the rest rocks are 11, 17, 21. The solution is optimal. You can try other methods to see the result.
Data Scaling
20%
0 ≤ M ≤ 10
0 ≤ M ≤ 10
1 ≤ L ≤ 1,000,000,000
30%
10 ≤ M ≤ 100
10 ≤ M ≤ 100
1 ≤ L ≤ 1,000,000,000
50%
100 ≤ M ≤ 50,000
100 ≤ M ≤ 50,000
1 ≤ L ≤ 1,000,000,000
Mention: You will see this Test your code Section when the problem is not available to test online, you may insert your codes on the template source code to implement algorithms in order to make the tester run dependablely.
How to test:
set
RUN_TEST = Truecopy the code file into directory
testing/run the code with command
python <file_name>.pyThen the testing code will automatically start and result will be given
P2678 Template (Do not change lines indicated by #, your code can be inserted into the main() or Solution class)
Brute Force: We can select any groups of M stones to be removed. And record the maximum interval of the minimal jump.
Linear Search: For the maximum interval of the minimal jump, actually we can adopt the greedy methodology. To try the answer(ans) from L to 1. If two adjacent rocks has interval shorter than ans, then remove the next rock. If the attemption time less than M. It is just the optimal solution.
Binary Search: It is obvious that the answer of the question is allocated between 1 and L. For all possibilities we can use binary search to reduce the complexity from $O(N)$ to $O(\log N)$. Try to write the code to adopt the binary search methodology similar to the given code.
Core Code