time complexity: O(logN)
1. 总觉得这两者有联系， 如果是sorted 的array的话，是可以进行binary search的，因为sorted array 是可以直接转化成一棵BST的，array里面的mid就是BST里面的root，left 和 right 对应着BST里面的left subtree 和right subtree. 那么 BST的 insert 和在 sorted array 里找 insert position 是不是也是相通的呢？是的。 如果以这种思路还看的话， 很容易理解为什么Insert position in sorted array最后返回的是Left了。 sorted array走到left == right的时候其实就是BST走到了 leaf node， 此时，要么插入在leaf node的左子树，要么插入在leaf node的右子树， 但是对于一个sorted array来说，它的长度只能在右边增长，左边界0是定的，所以对应在BST上看的话， left subtree上是不能加的，只能在右子树上加数， 这就意味着， 当left == right的时候，并且如果此时mid > target, 继续往左子树走，但是发现左子树为NULL，这对应着binary search 跳出了循环，此时不能往左边插，最多只能等于left, 所以返回Left，如果此时mid < target, 往右子树走，右子树为NULL，此时可以往右边插，正好对应此时的Left的值， 所以最后任何情况下都是返回Left就可以了。
sorted array to BST
basic binary search
insert position in sorted array.
2. Binary search in array, 分类：
2.1 按照这个array是否是sorted :
这个array可以是 sorted, 也可以不是sorted的，但是需要有一些规律。
case1: 如果这个array是sorted
basic binary search ： 其实就是普通的BST search target问题， 由于array是sorted的，所以每次根据target 和 mid的值，都能排除 一半的数字，时间复杂度O(logN)
binary search的变形： find first occurrence of target, find last occurrence of target,
2.2 按照binary search 的结束条件：
最常用的结束条件：
Left <= right / left < right-1
这两个结束条件有什么区别， 在决定用binary search做题的时候，应该考虑两个点：
- 如果利用Binary search 缩小目标范围？ 找到砍掉一半array的条件是什么？
- 一般需要把mid的值进行comparison:
- compare mid element with target
- compare mid element with left element
- compare mid element with right element
- compare mid element with its neighbors
- 结束条件怎么选？ left <= right ? or left < right-1?
- 依据什么来选择条件？我们从两个方面来进行比较：
- case1: 在把mid 进行comparison的时候，是否能够确定 mid 是答案，或者mid 一定不是答案？ 对于 left <= right, 这个是binary search 最classical 的结束条件， 每次比较之后，都可以确定mid是否为答案，Mid是答案， 返回mid， mid不是答案， mid-1/mid+1； 对于left < right-1， binary search 变种1.1， 1.2 , 每次比较，我们不能确定mid是否是答案，所以每次进行比较之后，Mid是include到下一轮比较中的，left = mid/right =mid, 最后条件结束， 会剩下left, right两个候选答案，再进行post processing 得到最后的答案。
eg: float sqrt(float input) --> 对于float/double型的数据的binary search， 是不会用left < right-1， 因为 不管Mid是否包含在最后答案里面，left 都不会 == mid， 所以v1.1, v1.2用在float/double里面是错误的。
这个题目利用上面总结的方法写感觉比之前做的那几遍逻辑都简单清晰很多，简单分析下这个题目是怎么应用上面总结的方法的。
首先这个rotated sorted array如果画个图分析下会看到明显的特征，其实我们只需要把mid跟right来相比，compare mid element with right element，因为这个最低点要么在mid-right之间，要么不在mid-right之间，跟left的关系还没有那么明显，所以我们可以确定 这个binary search里面comparison的关系了， 然后我们需要考虑condition了， 用哪种condition取决于 这个mid在做comparison的时候能不能直接判断包不包括在下一段search 区域内，如果不能，那么就用variant1.1， 否则用classic, 虽然这些条件判断并不是唯一的，但是用这样的方法写的话是最简单清晰而且容易理解的一种。 并不是说用variant 1.1的题目就不能用classic。 这种写法最保险，肯定不会出错。
int findMin(vector<int>& nums) {
if (nums.size() == 0) return -1;
int left = 0;
int right = nums.size()-1;
while (left < right -1) {
int mid = left + (right - left)/2;
if (nums[mid] < nums[right]) {
right = mid;
} else {
left = mid;
}
}
return (nums[left] < nums[right]) ? nums[left] : nums[right];
}
extension: Leetcode 154: find minimal element in rotated sorted array------contain duplicates
int findMin(vector<int>& nums) {
if (nums.size() == 0) return -1;
int left = 0;
int right = nums.size()-1;
while (left < right-1) {
int mid = left + (right-left)/2;
if (nums[mid] < nums[right]) {
right = mid;
} else if (nums[mid] == nums[right]){
right--;
} else {
left = mid;
}
}
return (nums[left] < nums[right]) ? nums[left] : nums[right];
}
small class-2.2.1
1. while(condition) {
compare mid element with possible candidates;
此时：
//需要考虑到所有可能的cases
//写程序的时候，千万不能漏掉可能的情况，如果漏掉可能的情况的话，很可能随便一个test case都能使程序 runtime error bug!
}
example: leetcode 162: find peak element + small class: find local minimal
int findPeakElement(vector<int>& nums) {
if (nums.size() == 0) return -1;
int left = 0;
int right = nums.size()-1;
while (left < right - 1) {
int mid = left + (right - left)/2;
if (nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1]) {
return mid;
}
if (nums[mid] > nums[mid-1]) {
left = mid;
} else {
// 这个地方不能写成if (nums[mid] > nums[mid+1])，这只是right = mid的一种情况，如果这样写，那么肯定是还有其他情况需要考虑，比如：nums[mid] < nums[mid+1]的情况，这种情况这样写并没有进行处理，所以最后程序就进入了死循环，会报runtime error的错误。
right = mid;
}
}
if (nums[left] > nums[right]) {
return left;
}
return right;
}
2. Post Processing 这个过程在有的题目里面需要好好分析才能写出正确的结果。有的题目不是那么容易分析出来
3. 对于bianry search那几种方法，均存在mid == left, mid == right, left == right的情况，解题时要注意分析这些临界情况下的折半方法。
int search(vector<int>& nums, int target) {
if (nums.size() == 0) return -1;
int left = 0;
int right = nums.size()-1;
while (left <= right) {
int mid = left + (right - left)/2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] >= nums[left]) { //mid == left的时候，可以把左边半段视为递增序列，不可能mid 到right的右半段递增，
if (target < nums[mid] && target >= nums[left]) {
right = mid-1;
} else {
left = mid + 1;
}
} else {
if (target <= nums[right] && target > nums[mid]) {
left = mid+1;
} else {
right = mid-1;
}
}
}
return -1;
}
- case2: 在binary search过程中关于corner case的考虑，对于 left <= right， 这个过程会需要考虑 left = mid, left = right, right = mid，因为这些情况都是会出现的； 对于left < right-1, 我们不需要考虑这些corner case, 因为都不会出现，但是对于这些corner case, 我们需要在preprocessing 和 post processing 过程中进行考虑。 所以，对于一些corner case特别多的情况，选用 Left < right -1可能逻辑会比较清晰。
这个题目利用上面总结的方法写感觉比之前做的那几遍逻辑都简单清晰很多，简单分析下这个题目是怎么应用上面总结的方法的。
首先这个rotated sorted array如果画个图分析下会看到明显的特征，其实我们只需要把mid跟right来相比，compare mid element with right element，因为这个最低点要么在mid-right之间，要么不在mid-right之间，跟left的关系还没有那么明显，所以我们可以确定 这个binary search里面comparison的关系了， 然后我们需要考虑condition了， 用哪种condition取决于 这个mid在做comparison的时候能不能直接判断包不包括在下一段search 区域内，如果不能，那么就用variant1.1， 否则用classic, 虽然这些条件判断并不是唯一的，但是用这样的方法写的话是最简单清晰而且容易理解的一种。 并不是说用variant 1.1的题目就不能用classic。 这种写法最保险，肯定不会出错。
int findMin(vector<int>& nums) {
if (nums.size() == 0) return -1;
int left = 0;
int right = nums.size()-1;
while (left < right -1) {
int mid = left + (right - left)/2;
if (nums[mid] < nums[right]) {
right = mid;
} else {
left = mid;
}
}
return (nums[left] < nums[right]) ? nums[left] : nums[right];
}
extension: Leetcode 154: find minimal element in rotated sorted array------contain duplicates
int findMin(vector<int>& nums) {
if (nums.size() == 0) return -1;
int left = 0;
int right = nums.size()-1;
while (left < right-1) {
int mid = left + (right-left)/2;
if (nums[mid] < nums[right]) {
right = mid;
} else if (nums[mid] == nums[right]){
right--;
} else {
left = mid;
}
}
return (nums[left] < nums[right]) ? nums[left] : nums[right];
}
small class-2.2.1
Given sorted int array, “rotated then reversed” first increasing. find the maximum value.
123456 -> 564321:
这个题目是上面rotated sorted array minimal的拓展，方法也是可以通过画图看出来，可以发现mid 元素和left元素跟maximum元素有很直接的关系， 可以把binary search 第一步找出来，即compare mid with left 判断下一个区间， 那么condition 怎么选择？ 由于Mid在每一步并不能有确定区间关系，所以使用variant1.1。
int RotatedMaximum (vector<int> &input) {
if (input.size() == 0) return -1;
int left = 0;
int right = input.size()-1;
while (left < right-1) {
int mid = left + (right-left)/2;
if (input[mid] < input[left]) {
right = mid;
} else {
left = mid;
}
}
return (input[left] > input[right]) ? input[left] : input[right];
}
2.2.2 Given sorted int array, first increasing then decreasing. find the maximum value.
这个题目和上面的题目的区别是：这个array并不是rotated的， 所以只通过比较left不能找到规律，但是可以通过比较Mid相邻元素，看mid是处于 升序 区间， 还是处于 降序 区间来判断maximum value存在的空间。
int SortedMaximum (vector<int> &input) {
if (input.size() == 0) return -1;
int left = 0;
int right = input.size()-1;
while (left < right-1) {
int mid = left + (right - left)/2;
if (input[mid] > input[mid-1] && input[mid] > input[mid+1]) {
return input[mid];
} else if (input[mid] > input[mid-1]) {
left = mid;
} else {
right = mid;
}
}
return (input[left] > input[right]) ? input[left] : input[right];
}
3. Missing Number, n sized array contains number from [1, n + 1] except one.
这个题目由于contain的number在[1,n+1]之间，并且如果都是unique number的话， 那么对解法就很有利，
M1： 最直接的解法： sum（n）--》 O（n）, 求和然后相减就能得到Missing的number
M2： hashMap, 把array里面的数全部存到unordered_map中，然后从1-》n+1遍历，如果unordered_map里面有没有找到的数，那么这个肯定是missing number O(N) + S(N)
M3： XOR，把这个数组里的[1-n+1]数（n+1除外）和 [1, n+1]的数进行一一XOR，那么这个missing number肯定只出现了一次，而其他数出现了两次，所以最后剩下的就是那个missing number
M4： swap, 把相应的元素swap到index对应的位置，然后遍历一遍数组就可以找出Missing number。最后这个方法并不局限于数字一定要出现在[1-n+1]，missing 的那个数字可以用其他数字任何一个数字代替。
int firstMissingPositive(vector<int>& nums) {
if (nums.size() == 0) return 1;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > 0 && nums[i] < nums.size()+1) {
if (nums[i] != nums[nums[i]-1]) {
swap(nums[i], nums[nums[i]-1]);
i--;
}
}
}
for (int i =0; i < nums.size(); i++) {
if (nums[i] != i+1) {
return i+1;
}
}
return nums.size()+1;
}
3.1 3的 extension，同样的题干，改变条件，解法就不一样了。The given array is sorted.
这个题目转化成了， sorted array, 直接用binary search来判断就好了。
同样的解法可以解决find insertion position in sorted array那个题目了。
由于array里的数字在1-n+1之间，所以肯定是从某个位置起，这些元素的位置偏移为1，binary search的砍半条件是 mid元素跟它自己的index - mid来比较，正常情况下，mid元素 = mid +1, 但是如果 = mid+2,说明此时元素已经有了位移。
int FirstMissing (vector<int> &input) {
if (input.size() == 0) return -1;
int left = 0;
int right = input.size()-1;
while (left < right-1) {
int mid = left + (right - left)/2;
if (input[mid] == mid +2) {
right = mid;
} else {
left = mid;
}
}
//post processing
if (input[left] == left+2) {
return left+1;
}
if (input[right] == right+2 ) {
return right+1;
}
return right+2;
}
4. Closest/first Occurrence/last Occurrence/ Smallest larger than/largest smaller than/.....
Build a service, such that it can answer this kind of query: what is the next XX number larger than target.
The queries are called multiple times.
Fibonacci Number:
1, 1, 2, 3, 5, 8, 13, 21
target = 6, return 8;
target = 12, return 13;
target = 25, return 34;
这个题目最直接的想法是： 对于一个target， 我们generate出 fibonacci serial numbers until we find such a number that is larger than target.
但是如果这个query要call 多次，每次都去找一个fibonacci序列的话，那么会有很多重复的运算，比如 target = 6, target = 12， call target = 12 的时候
5. 1D --> 2D
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:
[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]
find target ==> 两种方法：1. 先按照一位来找对应的row, 然后再对相应的row找target
2. 按照2D 坐标到1D坐标的转换
这两种时间复杂度都是O(logN + logM), 但是第二种方法比第一种方法更容易写， 所以第二种方法更优。
Binary search 的题目写code的时候特别需要注意的点：2. 按照2D 坐标到1D坐标的转换
这两种时间复杂度都是O(logN + logM), 但是第二种方法比第一种方法更容易写， 所以第二种方法更优。
1. while(condition) {
compare mid element with possible candidates;
此时：
//需要考虑到所有可能的cases
//写程序的时候，千万不能漏掉可能的情况，如果漏掉可能的情况的话，很可能随便一个test case都能使程序 runtime error bug!
}
example: leetcode 162: find peak element + small class: find local minimal
int findPeakElement(vector<int>& nums) {
if (nums.size() == 0) return -1;
int left = 0;
int right = nums.size()-1;
while (left < right - 1) {
int mid = left + (right - left)/2;
if (nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1]) {
return mid;
}
if (nums[mid] > nums[mid-1]) {
left = mid;
} else {
// 这个地方不能写成if (nums[mid] > nums[mid+1])，这只是right = mid的一种情况，如果这样写，那么肯定是还有其他情况需要考虑，比如：nums[mid] < nums[mid+1]的情况，这种情况这样写并没有进行处理，所以最后程序就进入了死循环，会报runtime error的错误。
right = mid;
}
}
if (nums[left] > nums[right]) {
return left;
}
return right;
}
2. Post Processing 这个过程在有的题目里面需要好好分析才能写出正确的结果。有的题目不是那么容易分析出来
3. 对于bianry search那几种方法，均存在mid == left, mid == right, left == right的情况，解题时要注意分析这些临界情况下的折半方法。
int search(vector<int>& nums, int target) {
if (nums.size() == 0) return -1;
int left = 0;
int right = nums.size()-1;
while (left <= right) {
int mid = left + (right - left)/2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] >= nums[left]) { //mid == left的时候，可以把左边半段视为递增序列，不可能mid 到right的右半段递增，
if (target < nums[mid] && target >= nums[left]) {
right = mid-1;
} else {
left = mid + 1;
}
} else {
if (target <= nums[right] && target > nums[mid]) {
left = mid+1;
} else {
right = mid-1;
}
}
}
return -1;
}
No comments:
Post a Comment