Binary search of even group
Topic describes
| source | The difficulty | Time complexity |
|---|---|---|
| Power button | difficult | O( log(n) ) |
Given two positively ordered (from small to large) arrays nums1 and nums2 of size m and n, respectively. Find and return the median of these two ordinal groups.
Example 1:
Input: nums1 = [1,3], nums2 = [2] output: 2.00000 explanation: merge array = [1,2,3], median 2
Example 2:
Input: nums1 = [1,2], nums2 = [3,4] output: 2.50000 explanation: merge array = [1,2,3,4], median (2 + 3) / 2 = 2.5
Example 3:
Input: nums1 = [0,0], nums2 = [0,0] output: 0.00000
Example 4:
Input: nums1 = [], nums2 = [1] Output: 1.00000
Example 5:
Input: nums1 = [2], nums2 = [] Output: 2.00000
Tip:
- nums1.length == m
- nums2.length == n
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- -106 <= nums1[i], nums2[i] <= 106
Source: LeetCode link: leetcode-cn.com/problems/me… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.
Analysis of the
If the problem does not require time and space complexity, through the most direct method can be passed. Given the size of the problem, m + n <= 2000, let’s say n = m + n, which is very small. So even order n log n time is fine.
According to the optimization degree of time complexity and space complexity, there are several solutions as follows.
| The solution | Time complexity | Spatial complexity |
|---|---|---|
| Direct merge sort + index lookup | O(N*log(N)) | O(N) |
| Merge merge sort + index lookup | O(N) | O(N) |
| Binary search method 1 | O(log(N)) | O(1) |
| Binary search method 2 | O(log(N)) | O(1) |
Solution 1: merge sort + search directly
That’s the easiest way to think about it. The steps are very specific.
- The array
nums1andnums2Merge into a new arraynums3. - The system function is zero
nums3Sort. - Looking for
nums3The median.
The time complexity of numS1 and NUMs2 merging is O(N), the sorting complexity is O(N*log(N)), and the space complexity is O(N) because another space needs to be created for merging and sorting. Finally, in the sorted NUMS3 to find the median, as long as the simple value of the median index, this part of the complexity of O(1).
In summary, the total time complexity of the algorithm is O(N*log(N)), and the space complexity is O(N).
Solution 2: merge merge sort + search
Nums3 = nums1 = nums2 = nums3 = nums1 = nums2 = nums3 = nums1 = nums2 = nums3
Since nums1 and NUMs2 are known to be individually sorted arrays, they can be merged into a new sorted array using the merge step of the classical sorting algorithm merge sort. The time complexity of the merge step is O(N).
The remaining steps are the same as in solution 1.
In conclusion, the total time complexity and space complexity of the algorithm are O(N) and O(N) respectively.
Solution 3: binary search method 1
Given that nums1 and NUMs2 are sorted arrays, it is not difficult to consider whether binary search can be used to locate the median of the merged array without merging.
Although the algorithm does not merge NUMs1 and nums2, it still assumes that the merged sorted array is NUMs3.
Take 0 as the initial subscript of the array index, then nums1 consists of nums1[0..
- when
m + nFor an even number, the median isnums3[(m+n)/2-1]andnums3[(m+n)/2]The average of theta. - when
m + nIs odd, the median isnums3[(m+n-1)/2].
Because nums3 cannot be merged directly (which would cause the complexity of the algorithm to become O(N)), in order to obtain the median without merging, you need to search directly from nums1[0..< I] and nums2[0..
It can be calculated that, for nums3, the median must exist within nums3[0..<(m+n)/2+1], where (m+n)/2 is the bottom integer.
Nums1 [0..< I] and nums2[0..
= I >= 0, m >= I >= 0, m >= I >= 0, M >= I >= 0.
Then, the problem of finding the median is transformed into the problem of finding I and j, and if I is known, then j is also known, because you can find it by m+n /2+1- I.
Nums1 [0..< I] and nums2[0..
The analysis is divided into three cases:
- when
m=0When,nums1Is an empty array. It’s not hard to figure out wheni=0andj=(m+n)/2+1When,nums1[0..<i]andnums2[0..<j]We want to find the subarray. - when
n=0, we can also conclude that wheni=(m+n)/2+1andj=0When,nums1[0..<i]andnums2[0..<j]We want to find the subarray. - when
m>0andn>0, if and only ifnums1[i-1]<=nums2[j-1]<=nums[i]Or,nums1[j-1]<=nums2[i-1]<=nums[j]When,nums1[0..<i]andnums2[0..<j]That’s the subarray we’re looking for.
To find nums1[0..< I] and nums2[0..
When moving I or J through dichotomy, the strategy of moving is:
- when
nums1[i]<nums2[j-1]When,nums1You can also move to the right, so you need to move to the rightiThe shift to the leftj. - when
nums2[j]<nums2[i-1]When,nums2You can also move to the right, so you need to move to the rightjThe shift to the lefti. - The “number of steps” of movement depends
nums1andnums2Move range, we choose the smaller move range to divide each time, otherwise the move will overflow, when the number of moves is determined, the other array can only move the same number of steps in the opposite direction, and so oni+jThe result is always the same.
And the following boundary cases need to be considered:
- when
iI need to move to the left buti=0When,nums1Are all less thannums2, directly returnnums2The corresponding subarray of. - when
jI need to move to the left butj=0When,nums2Are all less thannums1, directly returnnums1The corresponding subarray of.
When nums1[0..< I] and nums2[0..
- when
m+nWhen it’s odd, the median is equal tonums1[i-1].nums2[j-1]The largest value of two numbers (ignored if any of them does not exist because of the boundary problem). - when
m+nIf it’s an even number, the median is equal tonums1[i-1].nums1[i-2].nums2[j-1].nums2[j-2]Take the average value of the two largest of the four numbers (ignored if they don’t exist because of the boundary problem).
After the basic idea is finished, the next part is the code.
In order to make the algorithm clearer, the code is moderately encapsulated. First, because of the “custom” binary algorithm involved, encapsulate a structure to describe the search scope.
struct RANGE {
var begin = 0
var end = 0
var center = 0
mutating func set(_ b: Int._ e: Int._ c: Int) {
begin = b
end = e
center = c
}
}
Copy the codeDefine a CMP function that describes the case where a left shift is required, a right shift is required, or a subarray has been found.
func cmp(_ a: Int._ b: Int) -> Int {
guard a ! = -1 && b ! = -1 else { return 0 }
if nums1[a] > = nums2[b] {
return b + 1 > = nums2.count || nums2[b+1] > = nums1[a] ? 0 : 1
}
return a + 1 > = nums1.count || nums1[a+1] > = nums2[b] ? 0 : -1
}
Copy the codeDefine a mov function to handle subarray movement, so that when one subarray range is moved to one side, the other subarray must be moved in the opposite direction.
func mov(_ r1: inout RANGE._ r2: inout RANGE._ mv: Int) {
r1.end = r1.center
r1.center - = mv
r2.begin = r2.center + 1
r2.center + = mv
}
Copy the codeNow comes the most important part of the search. The search() function returns a range value, and the results are the respective subarray results of nums1 and nums2. Slightly different from the previous description, the result is returned with the index of the last number in the subarray. If one of the subarrays does not exist, the subscript is returned -1.
func search(a)- > (Int.Int) {
let n = (nums1.count + nums2.count) / 2 + 1
if nums1.isEmpty {
return (-1, n - 1)}else if nums2.isEmpty {
return (n-1.-1)}var range1 = RANGE(a)var range2 = RANGE(a)if nums1.count < nums2.count {
range1.set(0, nums1.count, nums1.count / 2)
range2.set(0, nums2.count, n - 2 - range1.center)
} else {
range2.set(0, nums2.count, nums2.count / 2)
range1.set(0, nums1.count, n - 2 - range2.center)
}
var t = cmp(range1.center, range2.center)
while t ! = 0 {
if t > 0 {
var mv = 0
if range1.center - range1.begin < range2.end - 1 - range2.center {
mv = (range1.center - range1.begin + 1) / 2
} else {
mv = (range2.end - range2.center) / 2
}
guard mv ! = 0 else { return (-1, n-1) }
mov(&range1, &range2, mv)
} else {
var mv = 0
if range1.end - 1 - range1.center < range2.center - range2.begin {
mv = (range1.end - range1.center) / 2
} else {
mv = (range2.center - range2.begin + 1) / 2
}
if mv = = 0 {
return (n-1.-1)
}
mov(&range2, &range1, mv)
}
t = cmp(range1.center, range2.center)
}
return (range1.center, range2.center)
}
Copy the codeFinally, the answer function is used to calculate the median given that two subarrays are returned.
func answer(_ s: (Int.Int)) -> Double {
var m1 = Int(Int32.min)
var m2 = Int(Int32.min)
if (nums1.count + nums2.count) % 2 = = 0 {
if s.0 ! = -1 {
m1 = nums1[s.0]
if s.0 > 0 { m2 = nums1[s.0-1]}if m2 > m1 { swap(&m1, &m2) }
}
if s.1 ! = -1 {
if nums2[s.1] > m2 { m2 = nums2[s.1]}if m2 > m1 { swap(&m1, &m2) }
if s.1 > 0 && nums2[s.1-1] > m2 { m2 = nums2[s.1-1]}if m2 > m1 { swap(&m1, &m2) }
}
} else {
if s.0 ! = -1 { m1 = nums1[s.0]}if s.1 ! = -1 { m1 = max(m1, nums2[s.1]) }
m2 = m1
}
return (Double(m1) + Double(m2)) / 2.0
}
let s = search()
return answer(s)
}
Copy the codeThe overall code is as follows:
class Solution {
func findMedianSortedArrays(_ nums1: [Int]._ nums2: [Int]) -> Double {
struct RANGE {
var begin = 0
var end = 0
var center = 0
mutating func set(_ b: Int._ e: Int._ c: Int) {
begin = b
end = e
center = c
}
}
func cmp(_ a: Int._ b: Int) -> Int {
guard a ! = -1 && b ! = -1 else { return 0 }
if nums1[a] > = nums2[b] {
return b + 1 > = nums2.count || nums2[b+1] > = nums1[a] ? 0 : 1
}
return a + 1 > = nums1.count || nums1[a+1] > = nums2[b] ? 0 : -1
}
func mov(_ r1: inout RANGE._ r2: inout RANGE._ mv: Int) {
r1.end = r1.center
r1.center - = mv
r2.begin = r2.center + 1
r2.center + = mv
}
func search(a)- > (Int.Int) {
let n = (nums1.count + nums2.count) / 2 + 1
if nums1.isEmpty {
return (-1, n - 1)}else if nums2.isEmpty {
return (n-1.-1)}var range1 = RANGE(a)var range2 = RANGE(a)if nums1.count < nums2.count {
range1.set(0, nums1.count, nums1.count / 2)
range2.set(0, nums2.count, n - 2 - range1.center)
} else {
range2.set(0, nums2.count, nums2.count / 2)
range1.set(0, nums1.count, n - 2 - range2.center)
}
var t = cmp(range1.center, range2.center)
while t ! = 0 {
if t > 0 {
var mv = 0
if range1.center - range1.begin < range2.end - 1 - range2.center {
mv = (range1.center - range1.begin + 1) / 2
} else {
mv = (range2.end - range2.center) / 2
}
guard mv ! = 0 else { return (-1, n-1) }
mov(&range1, &range2, mv)
} else {
var mv = 0
if range1.end - 1 - range1.center < range2.center - range2.begin {
mv = (range1.end - range1.center) / 2
} else {
mv = (range2.center - range2.begin + 1) / 2
}
if mv = = 0 {
return (n-1.-1)
}
mov(&range2, &range1, mv)
}
t = cmp(range1.center, range2.center)
}
return (range1.center, range2.center)
}
func answer(_ s: (Int.Int)) -> Double {
var m1 = Int(Int32.min)
var m2 = Int(Int32.min)
if (nums1.count + nums2.count) % 2 = = 0 {
if s.0 ! = -1 {
m1 = nums1[s.0]
if s.0 > 0 { m2 = nums1[s.0-1]}if m2 > m1 { swap(&m1, &m2) }
}
if s.1 ! = -1 {
if nums2[s.1] > m2 { m2 = nums2[s.1]}if m2 > m1 { swap(&m1, &m2) }
if s.1 > 0 && nums2[s.1-1] > m2 { m2 = nums2[s.1-1]}if m2 > m1 { swap(&m1, &m2) }
}
} else {
if s.0 ! = -1 { m1 = nums1[s.0]}if s.1 ! = -1 { m1 = max(m1, nums2[s.1]) }
m2 = m1
}
return (Double(m1) + Double(m2)) / 2.0
}
let s = search()
return answer(s)
}
}
Copy the codeSolution 3: binary search method 2
Method 2 of binary search for a dual set of numbers has a similar policy to method 1, except that it defines the search function findValueAtIndex to search for the KTH element of nums3 composed of nums1 and nums2. The implementation strategy of this function is binary binary.
With this function, we can easily get the median.
The source code is as follows.
// Order log(n)) complexity solution 2
class Solution {
class Scope {
var begin = 0
var end = 0
var center: Int { !valid ? -1 : (begin + end) / 2 }
var valid: Bool { end > begin }
var count: Int { end - begin }
func moveRight(a) { begin = center }
func moveLeft(a) { if valid { end = center } }
}
func findMedianSortedArrays(_ nums1: [Int]._ nums2: [Int]) -> Double {
func findValueAtIndex(_ index: Int) -> Int {
let scope1 = Scope(a)let scope2 = Scope()
scope1.end = nums1.count
scope2.end = nums2.count
while scope1.valid || scope2.valid {
let v1 = scope1.valid ? nums1[scope1.center] : Int.min
let v2 = scope2.valid ? nums2[scope2.center] : Int.min
let currentIndex = scope1.center + scope2.center + 1
if v1 < v2 {
if currentIndex = = index {
if scope1.valid && scope1.center + 1 < scope1.end && nums1[scope1.center+1] < nums2[scope2.center] {
scope2.moveLeft()
} else {
return nums2[scope2.center]
}
} else if currentIndex < index {
scope1.count < = 1 ? scope2.moveRight() : scope1.moveRight()
} else if currentIndex > index {
scope2.moveLeft()
}
} else {
if currentIndex = = index {
if scope2.valid && scope2.center + 1 < scope2.end && nums2[scope2.center+1] < nums1[scope1.center] {
scope1.moveLeft()
} else {
return nums1[scope1.center]
}
} else if currentIndex < index {
scope2.count < = 1 ? scope1.moveRight() : scope2.moveRight()
} else {
scope1.moveLeft()
}
}
}
return 0
}
let c1 = nums1.count
let c2 = nums2.count
if (c1 + c2) % 2 = = 0 {
let i1 = (c1 + c2) / 2
let i2 = i1 - 1
let v1 = findValueAtIndex(i1)
let v2 = findValueAtIndex(i2)
return (Double(v1) + Double(v2)) / 2.0
} else {
let i = (c1 + c2) / 2
let value = findValueAtIndex(i)
return Double(value)
}
}
}
Copy the codeconclusion
In order to solve the problem in order (1) space and order log(n) time, you have to do a binary search on both arrays without reordering them.
There is a very clever code solution to the problem of force button, but after looking at the basic idea, I provide a third and fourth solution, plus the language skills can make the code more concise.
Follow my public number fenghai causeway technology jun click on the group button to join the force buckle problem communication group.
The source code is available on github: github.com/FengHaiTong…