function binarySearch(arr, target, i, j) {
if (i === j) {
return arr[i] === target;
} else {
const rest = (i + j) / 2;
if (arr[rest] === target) return true;
else if (arr[rest] > target) {
return binarySearch(arr, target, rest, i);
} else {
return binarySearch(arr, target, i, rest);
}
}
}
Recursion（递归）: A procedure that calls itself one or multiple times, on different inputs.
Running Time: O(log n)
Example to calculate it:
T(n) <= T(n / 2) + 4
==> T(n / 4) + 8
…
==> T(n / 2^i) + 4i
…
==> T(n / 2^log(n) -1) + 4(logn - 1)
==> log n
Split the input into smaller sub-instances.
Solve each sub-instance separately.
Combine the solutions of the sub-instances into a solution for the problem.
Often: For each sub-instance, the algorithm calls itself to solve it (recursion).
The instances become so small that they can be solved via a brute force algorithm.
Given an array of n numbers, a majority element is one that appears more than n/2 times in the array.
(Ignoring rounding issues, otherwise ceil(n/2) times).
Example
function Majority(arr) {
const len = arr.length;
const res = [];
if (len === 0) return false;
for (let i = 1; i <= len / 2; i++) {
if (arr[2 * i - 2] === arr[2 * i - 1]) {
res.push(arr[2 * i - 1]);
}
}
return res;
}
// [10, 6, 10]
x is a majority element in A, then x is a majority element in B.Proof of correctness of Majority (assuming Lemma): By induction:
Base case: Majority(B) works correctly for array B of size 1.
Inductive step: Assume that Majority(B) works correctly for array B of size smaller than |A| (inductive hypothesis).
Case 1 (There is a majority element in A): Then by the Lemma, it is also a majority element in B. Majority(B) will output it, by the inductive hypothesis and the last step of Majority(A) will output it.
Case 2 (There is not a majority element in A): Then the last step of Majority(A) will reject any candidate majority elements returned from Majority(B).
We want to prove that statement S is true.
We assume that the statement is not true.
We reach a conclusion which cannot possibly be true.
Assumption: Suppose to the contrary, that x is a majority element in A but not a majority element in B.
Let m be the number of occurrences of x in A.
Let k be the number of occurrences of x in B.
By the assumption, it follows that other values appear at least k times in B.
This means that other values appear in A at least:
2k times from the pairs that are represented in B by a value different than x plus
m-2k times, since each occurrence of x in A that is not paired with another x is paired with
some other value (since there are 2k pairs xx, there are m-2k other occurrences of x in A).
In total, this gives 2k+(m-2k) = m occurrences, which contradicts the fact that x is a majority in A.
n