花花酱的lower_bound/upper_bound讲解，真的好，万能模板，而且通过源码加深印象。
值得注意的是，这里的r要取length而不是length - 1才能让upper_bound在搜索超出边界的数的时候返回len而不是len - 1（可参考我的代码611. Valid Triangle Number）。
在做1498题的二分写法的时候又一次发现，hi不能写成n-1，因为upper_bound的i是可以=n的，比如要找的target>A[n-1]的时候，就需要返回n，如果写成n-1，就只能返回n-1了。因为平时用upper_bound比较少，lower_bound比较多，所以这一点需要特别注意。
那么，如果你是要取数组中的某个数字，那就不能把r定位length，否则就会越界。
**[disclaimer]以下内容整理自leetcode topics
Template I
int binarySearch(int[] nums, int target){
if(nums == null || nums.length == 0)
return -1;
int left = 0, right = nums.length - 1;
while(left <= right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if(nums[mid] == target){ return mid; }
else if(nums[mid] < target) { left = mid + 1; }
else { right = mid - 1; }
}
// End Condition: left > right
return -1;
}
Template #1 is used to search for an element or condition which can be determined by accessing a single index in the array.
Key Attributes:
- Most basic and elementary form of Binary Search
- Search Condition can be determined without comparing to the element's neighbors (or use specific elements around it)
- No post-processing required because at each step, you are checking to see if the element has been found. If you reach the end, then you know the element is not found
Distinguishing Syntax:
- Initial Condition: left = 0, right = length-1
- Termination: left > right
- Searching Left: right = mid-1
- Searching Right: left = mid+1
Template II
int binarySearch(int[] nums, int target){
if(nums == null || nums.length == 0)
return -1;
int left = 0, right = nums.length;
while(left < right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if(nums[mid] == target){ return mid; }
else if(nums[mid] < target) { left = mid + 1; }
else { right = mid; }
}
// Post-processing:
// End Condition: left == right
if(left != nums.length && nums[left] == target) return left;
return -1;
}
Template #2 is an advanced form of Binary Search. It is used to search for an element or condition which requires accessing the current index and its immediate right neighbor's index in the array.
**经验：l = mid + 1; r = mid;这个永远不会变，但是>=/<=/>/<这个要看情况。另外，r = length -1还是length也要看情况，这个的区别就是如果len是偶数,r = len + 1会取中间两个数右边那个。
Key Attributes:
- Search Condition needs to access element's immediate right neighbor
- Use element's right neighbor to determine if condition is met and decide whether to go left or right
- Gurantees Search Space is at least 2 in size at each step
- Post-processing required. Loop/Recursion ends when you have 1 element left. Need to assess if the remaining element meets the condition.
Distinguishing Syntax:
- Initial Condition: left = 0, right = length
- Termination: left == right
- Searching Left: right = mid
- Searching Right: left = mid+1
Template III
int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0)
return -1;
int left = 0, right = nums.length - 1;
while (left + 1 < right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid;
} else {
right = mid;
}
}
// Post-processing:
// End Condition: left + 1 == right
if(nums[left] == target) return left;
if(nums[right] == target) return right;
return -1;
}
Template #3 is used to search for an element or condition which requires accessing the current index and its immediate left and right neighbor's index in the array.
Key Attributes:
- Search Condition needs to access element's immediate left and right neighbors
- Use element's neighbors to determine if condition is met and decide whether to go left or right
- Gurantees Search Space is at least 3 in size at each step
- Post-processing required. Loop/Recursion ends when you have 2 elements left. Need to assess if the remaining elements meet the condition.
Distinguishing Syntax:
- Initial Condition: left = 0, right = length-1
- Termination: left + 1 == right
- Searching Left: right = mid
- Searching Right: left = mid
