Binary Search 解题模板
https://leetcode.com/articles/introduction-to-binary-search/
注意：需要考虑数组里是否有重复值
//check if the array is valid
if(nums==null||nums.length==0) return result;
//check if the matrix is valid
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return false;
34. Search for a Range
https://leetcode.com/problems/search-for-a-range/description/
思路：先找左边界，再找右边界
注意：target=nums[mid]时的处理方法不同；给startpoint和endpoint赋值时判断left和right的顺序不同。
public int[] searchRange(int[] nums, int target) {
int[] result = {-1, -1};
if(nums==null||nums.length==0) return result;
int startpoint, endpoint;
int left=0, right=nums.length-1, mid;
//find start position, when target=nums[mid], right position come down
while(left+1<right){
mid=left+(right-left)/2;
if(target>nums[mid]){
left=mid;
}else right=mid;
}
if(target==nums[left]) startpoint=left;
else if(target==nums[right]) startpoint=right;
else return result;
//find end position, when target=nums[mid], left position come up
left=0;
right=nums.length-1;
while(left+1<right){
mid=left+(right-left)/2;
if(target<nums[mid]){
right=mid;
}else left=mid;
}
//judge right range first
if(target==nums[right]) endpoint=right;
else endpoint=left;
result[0]=startpoint;
result[1]=endpoint;
return result;
}
162. Find Peak Element
思路: You may imagine that nums[-1] = nums[n] = -∞.
如果中间值不是峰值，那么在比它大的临近数一侧一定有峰值。
- mid是峰值：
[2 3 3] - mid不是峰值：
[2 3 4] -> left=mid
[4 3 2] -> right=mid
public int findPeakElement(int[] nums) {
int left=0, right=nums.length-1, mid;
while(left+1<right){
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 right=mid;
}
if(nums[left]>nums[right]) return left;
else return right;
}
35. Search Insert Position
- target在数组中
[1, 2, 3, 4] 2 - target不在数组中，target比数组中最大的数小，比最小的数大
[1, 2, 4] 2 - target不在数组中，target比数组中最大的数大
- target不在数组中，target比数组中最小的数小
注意：left+1<right时，考虑数组长度是2的情况。
public int searchInsert(int[] nums, int target) {
if(nums.length==0) return 0;
int left=0, right=nums.length-1, mid;
while(left+1<right){
mid=left+(right-left)/2;
if(nums[mid]<target) left=mid;
else right=mid;
}
if(nums[right]<target) return right+1;
else if(nums[left]>=target) return left;
else return right;
}
744. Find Smallest Letter Greater Than Target
duplicated sorted array, like ["e","e","e","e","e","e","n","n","n","n"]，当target=letters[mid]时，注意应该让left=mid还是right=mid。
在这道题里，如果让left=mid， ["e","e","e","e","e","e","n","n","n","n"]，最后left和right指向最左边，找不到比e大的元素是谁。
public char nextGreatestLetter(char[] letters, char target) {
int left=0, right=letters.length-1, mid;
while(left+1<right){
mid=left+(right-left)/2;
//judge when target=letters[mid]
if(target>=letters[mid]){
left=mid;
}else right=mid;
}
if(target>=letters[right]||target<letters[left]){
return letters[0];
}else return letters[right];
}
[349] Intersection of Two Arrays
[350] Intersection of Two Arrays II
[441] Arranging Coins
累加求和公式：sum = (1+x)*x/2
public int arrangeCoins(int n) {
if(n==0||n==1) return n;
int left=1, right=n, mid;
while(left+1<right){
mid=left+(right-left)/2;
//mid的类型一定要是long
long multi = (long)mid*(mid+1)/2;
if(multi<=n) left=mid;
else right=mid;
}
return left;
}
[367] Valid Perfect Square (pass)
class Solution {
public boolean isPerfectSquare(int num) {
int left=0, right=num, mid;
while(left+1<right){
mid=left+(right-left)/2;
long result=(long)mid*mid;
if(result<=num) left=mid;
else right=mid;
}
if(left*left==num || (long)right*right==num) return true;
else return false;
}
}
[287] Find the Duplicate Number
解法一：O(NlogN)
抽屉原理，以index作为mid标准，遍历数组计算有多少<=mid的元素，移动left和right指针。
class Solution {
public int findDuplicate(int[] nums) {
int left=0, right=nums.length-1, mid, n;
while(left+1<right){
for(int i=0; i<nums.length-1; i++){
if(nums[i]<=mid) n++;
}
if(n<=mid) left=mid;
else right=mid;
}
return right;
}
}
解法二：（待补充）Linked-List
33. Search in Rotated Sorted Array
no duplicate
- [4 5 6 7 0 1 2] left<mid
target=4: target在左边范围内，right=mid
target=2: target在右边范围内，left=mid - [5 6 7 0 1 2 4] left>mid
target=4: target在右边范围内，left=mid
target=2: target在左边范围内， right=mid
class Solution {
public int search(int[] nums, int target) {
if(nums==null||nums.length==0) return -1;
int left=0, right=nums.length-1, mid;
while(left+1<right){
mid=left+(right-left)/2;
//left<mid
if(nums[left]<nums[mid]){
if(nums[left]<=target && nums[mid]>=target) right=mid;
else left=mid;
//left>mid
}else{
if(nums[right]>=target && nums[mid]<target) left=mid;
else right=mid;
}
}
if(nums[right]==target) return right;
else if(nums[left]==target) return left;
else return -1;
}
}
[81] Search in Rotated Sorted Array II
- [2 2 5 6 0 0 1] left<mid
target=2: target在左边，right=mid
target=1: target在右边，left=mid - [2 5 6 0 0 1 2] left>mid
target=2: target在右边，left=mid
target=1: target在左边，right=mid - [2 3 5 2 2 2 2] left=mid
left++ (不知道怎么想出来这一步的)
class Solution {
public boolean search(int[] nums, int target) {
if(nums==null||nums.length==0) return false;
int left=0, right=nums.length-1, mid;
while(left+1<right){
mid=left+(right-left)/2;
if(nums[left]<nums[mid]){
if(target>=nums[left] && target<=nums[mid]) right=mid;
else left=mid;
}else if(nums[left]>nums[mid]){
if(target>nums[mid] && target<=nums[right]) left=mid;
else right=mid;
}else{
left++;
}
}
if(nums[left]==target || nums[right]==target) return true;
else return false;
}
}
153. Find Minimum in Rotated Sorted Array
no duplicate
left<right return left 最左小于最右时，数组没有旋转过，最小值是最左边。
- mid>left mid>right
[4 5 6 7 0 1 2] mid>mid-1 mid>mid+1 left=mid
[2 4 5 6 7 0 1] mid>mid-1 mid<mid+1 left=mid - mid>left mid<right
[0 1 2 4 5 6 7] right=mid - mid<left mid<right
[5 6 7 0 1 2 4]
[6 7 0 1 2 4 5]
right=mid;
class Solution {
public int findMin(int[] nums) {
int left=0, right=nums.length-1, mid;
if(nums[left]<nums[right]) return nums[left];
while(left+1<right){
mid=left+(right-left)/2;
//第一种情况
if(nums[mid]>nums[left] && nums[mid]>nums[right]) left=mid;
//剩下两种情况
else right=mid;
}
if(nums[left]<nums[right]) return nums[left];
else return nums[right];
}
}
154. Find Minimum in Rotated Sorted Array II
have duplicate
多了一种情况：left=mid left++
class Solution {
public int findMin(int[] nums) {
int left=0, right=nums.length-1, mid;
if(nums[left]<nums[right]) return nums[left];
while(left+1<right){
mid=left+(right-left)/2;
//第一种情况
if(nums[mid]>nums[left] && nums[mid]>nums[right]) left=mid;
//多出来的那种情况
else if(nums[mid]==nums[left]) left++;
//剩下两种情况
else right=mid;
}
if(nums[left]<nums[right]) return nums[left];
else return nums[right];
}
}
[378] Kth Smallest Element in a Sorted Matrix （重做）
java matrix
public static void main(String[] args) {
int[][] A=new int[][]{{1,2},{4,5},{7,8,10,11,12},{}};
System.out.println(A.length);//4,表示数组的行数
System.out.println(A[0].length);//2，表示对应行的长度
System.out.println(A[1].length);//2
System.out.println(A[2].length);//5
}
因为这个矩阵没有按照从小到大的顺序，所以不能按照index来做二分。
用数值大小的中间值做二分。
思路：这种不以矩阵内数字划分的问题最好用left<right来做
[74] Search a 2D Matrix
log(M*N)=logM+logN 直接当成一个array来找即可。
class Solution {
//O(log(M*N))
public boolean searchMatrix(int[][] matrix, int target) {
//check if the matrix is valid
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return false;
int row=matrix.length;
int col=matrix[0].length;
int left=0, right=row*col-1, mid;
while(left+1<right){
mid=left+(right-left)/2;
if(target<matrix[mid/col][mid%col]) right=mid;
else left=mid;
}
return (target==matrix[left/col][left%col] || target==matrix[right/col][right%col]);
}
}
240. Search a 2D Matrix II
- binary search
思路：找特征点，左下角和右上角两个点，以左下角的点为例，比它大的数都在右边，比它小的数都在它上边。
参考：https://zhuanlan.zhihu.com/p/29555088
O((m2+n2)^1/2)
// runtime: 16ms
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix==null||matrix.length==0||matrix[0]==null||matrix[0].length==0) return false;
int m=matrix.length-1, n=0, divide;
while(m>=0 && n<=matrix[0].length-1){
divide=matrix[m][n];
if(divide==target) return true;
else if(divide<target) n++;
else m--;
}
return false;
}
}
