二丶二分查找算法

算法"/>

二丶二分查找算法

文章目录

• • 59 螺旋矩阵
  • 34. 在排序数组中查找元素的第一个和最后一个位置
  • 35 搜索插入位置
  • 704. 二分查找
  • 74. 搜索二维矩阵
  • 162. 寻找峰值
  • 33. 搜索旋转排序数组 （其实两种条件下的二分查找法）
  • 153. 寻找旋转排序数组中的最小值
  • 88. 合并两个有序数组
  • 4. 寻找两个有序数组的中位数---(很重要)
  • 189. 旋转数组

注意：一般题目提到找第一个或者最后一个的情况，使用二分法，
二分查找算法的前提：必须是有序的，而且灭有重复元素的列表
步骤记忆：

1. 等于数值：按照code方式记忆
2. 第一个大于数值和第一个小于数值有两点：

• 第一个小于数值是相反的

 if(nums[mid] > target){start = mid;}else{end = mid;}

• 写第一个比target大的数，和第一个比target小的数的共同点:
  比taget大的数：return Math.max(nums[start],nums[end]);
  比target小的数：return Math.min(nums[start],nums[end]);
  只不过35需要对边界进行判断

public class 二分查找模板 {int binarySearch(int[] nums, int start, int end, int target){// 错误输入条件if (nums.length == 0 || start > end)return -1;// int start = 0, end = len - 1;   //当函数参数不包括start, end时while (start + 1 < end) { //注意这里是start+1，是<不是<=int mid = start + (end - start) / 2;// 注意： =, <, > 三种情况，mid 不+1也不-1if (nums[mid] == target) {// 寻找最后一个重复元素位置// start = mid;// 寻找第一个重复元素位置// end = mid;// 注释掉return  之后在while之后进行判断 ifreturn mid;} else if (nums[mid] < target) {start = mid;} else {end = mid;}}// 注意，循环结束后，单独处理start和endif (nums[start] == target) {return start;}if (nums[end] == target) {return end;}return -1;}
}

59 螺旋矩阵

class Solution {public int[][] generateMatrix(int n) {int l =0,r = n-1, t = 0,b =n-1;int retNum = n*n;int count =1;int[][] nums = new int[n][n];while(count <= retNum){for(int i =l;i <= r;i++) nums[t][i] = count++;t++;for(int i = t;i <= b;i++) nums[i][r] = count++;r--;for(int i = r;i >=l;i--) nums[b][i] = count++;b--;for(int i= b;i >= t;i--) nums[i][l] = count++;l++;}return nums;}}

34. 在排序数组中查找元素的第一个和最后一个位置

思路：直接使用两次二分法进行查找
注意：下面这一步。
if(nums[left] != target && nums[right] != target) {
return new int[]{-1, -1};
}
易错：查找最后一个位置的时候
1.按照模板来写比较好。就是下面这种写法
2.最后处理left和right先比较的right，然后在比较的是left

public static int[] searchRange(int[] nums, int target) {int[] res = new int[2];if(nums == null || nums.length == 0){return new int[]{-1,-1};}int start = 0,end = nums.length -1;//查找第一个位置while(start + 1 < end){int mid = start + (end - start)/2;if(nums[mid] == target){end = mid;}else if(nums[mid] > target){end = mid;}else{start = mid;}}if(nums[start] == target){res[0] = start;}else if(nums[end] == target){res[0] = end;}else {res[0] = -1;}start = 0;end = nums.length -1;while(start + 1 < end){int mid = start + (end -start)/2;if(nums[mid] == target){start = mid;}else if(nums[mid] < target){start = mid;}else{end = mid;}}if(nums[end] == target){res[1] = end;}else if(nums[start] == target){res[1] = start;}else{res[1] = -1;}return res;}

35 搜索插入位置

思路：查找第一个比target位置大的数。

class Solution {public int searchInsert(int[] nums, int target) {if(nums==null||nums.length==0){throw new RuntimeException("no");}int start =0;int end =nums.length-1;while(start+1<end){int mid =start+(end-start)/2;if(nums[mid]==target){return mid;}else if(nums[mid] < target){start = mid;}else if(nums[mid] > target){end =mid;}}if(nums[start]>=target){return start;}if(nums[end]>=target){return end;}else{ // 没有查找到比他大的数，直接插入到最后面，这里也可以等价于return nums.length-1；return end+1;}}
}

704. 二分查找

class Solution {public int search(int[] nums, int target) {if(nums==null||nums.length==0){return -1;}int start =0;int end =nums.length-1;while(start+1<end){int mid =start+(end-start)/2;if(nums[mid]==target){return mid;}else if(nums[mid] < target){start = mid;}else if(nums[mid] > target){end =mid;}}if(nums[start]==target){return start;}if(nums[end]==target){return end;}return -1;}
}

74. 搜索二维矩阵

注意：
1.二维数组的判断，易错。
2.第一次查找是找最后一个小于等于他的数。
3.对于两个变量 int start = 0 ,end = row * column-1; //特别注意中间的逗号。
4.还有row判断的时候最后start和end的先后顺序，因为是查找最后一个，所以先判断end。在start。

public class Solution {public boolean searchMatrix(int[][] matrix, int target) {if((matrix==null||matrix.length==0)||(matrix.length==1&&matrix[0].length==0)){return false;}int row = matrix.length;int column = matrix[0].length;// find the row index, the last number <= target int start = 0, end = row - 1;while (start + 1 < end) {int mid = start + (end - start) / 2;if (matrix[mid][0] == target) {return true;} else if (matrix[mid][0] < target) {start = mid;} else {end = mid;}}if (matrix[end][0] <= target) {row = end;} else if (matrix[start][0] <= target) {row = start;} else {return false;}// find the column index, the number equal to targetstart = 0;end = column - 1;while (start + 1 < end) {int mid = start + (end - start) / 2;if (matrix[row][mid] == target) {return true;} else if (matrix[row][mid] < target) {start = mid;} else {end = mid;}}if (matrix[row][start] == target) {return true;} else if (matrix[row][end] == target) {return true;}return false;}
}

解法二：看成一个一维数组。

class Solution {public  boolean searchMatrix(int[][] matrix, int target) {if(matrix == null || matrix.length == 0 || (matrix.length == 1 && matrix[0].length == 0)){return false;}int row = matrix.length;int column = matrix[0].length;int start = 0 ,end = row * column-1;while(start + 1 <end){int mid = start + (end -start)/2;int number = matrix[mid/column][mid%column];if(number == target){return true;}else if(number < target){start =mid;}else{end =mid;}}if(matrix[start/column][start%column]==target){return true;}if(matrix[end/column][end%column]==target){return true;}return false;}}

162. 寻找峰值

注意：最后比值的时候：是start和end之间相比的。
首先将数组看作是交替的升序和降序序列。

class Solution {public int findPeakElement(int[] nums) {if(nums == null || nums.length == 0){throw new IllegalArgumentException("no");}int start = 0,end = nums.length - 1;while(start + 1 < end){int mid = start + (end - start) / 2;if(nums[mid] < nums[mid + 1]){  //则峰值应该在右边start = mid;}else if (nums[mid] > nums[mid + 1]){  //则峰值应该在左边end = mid;}}//最后start和mid一定在相邻的位置if(nums[start] > nums[end]){return start;}return end;}
}

33. 搜索旋转排序数组 （其实两种条件下的二分查找法）

思路：旋转后的数组，如下图所示，然后看作是两个二分法，

注意： if(nums[start] <= target && target < nums[mid] ) ：保证在第一个s-m之间，然后前面的是一个升序数组，后半部分又是一个旋转数组，然后进行迭代。
然后： if(nums[mid]< target && target<= nums[end] ：保证在M-E之间，然后后面的是一个升序数组，前半部分又是一个旋转数组，然后进行迭代。

还有：注意第一个和第四个的等号是不能省略的，但是2,和3是可以省略的。
注意：上面说的等号问题又错一次

class Solution {public int search(int[] nums, int target) {if(nums == null || nums.length == 0){return -1;}int start = 0,end = nums.length - 1;while(start + 1 < end){int mid = start + (end - start)/2;if(nums[mid] == target){return mid;}if( nums[mid] > nums[start]){ //此时是Mid在绿线的位置if(nums[start] <= target &&  target < nums[mid] ){end = mid;}else{  //上面的if其实就是排除s -m之间的这段，其他的任何情况，我都可以将mid放在start；start = mid;}}else{  //此时Mid在红线的位置if(nums[mid]< target && target<= nums[end] ){start = mid;}else {end = mid;}}}if(nums[start] ==target){return start;}if(nums[end] == target){return end;}return -1;}
}

153. 寻找旋转排序数组中的最小值

思路：寻找第一个比target小的数，即可，
因为这是个旋转排序数组，所以第一个小于最右边的值，一定是最小值。而找到这个最小值的方法就是利用二分法，把最右边的值设成target，1.如果med的值大于最右边，则说明我们要找的值在med右边，所以start=med；
2.如果med的值小于最右边，则说明我们要找的值在med左边，所以end=med;

注意：记住二分法，mid的位置，
还有最后start和end的处理
注意：这道题旋转数组的处理和传统的模板方法中的end和start的处理是相反的

class Solution {public int findMin(int[] nums) {if(nums == null || nums.length == 0){throw new IllegalArgumentException("no");}int start = 0,end = nums.length-1;int target = nums[nums.length -1];while(start + 1 < end){int mid = start + (end - start) /2;if(nums[mid] > target){start = mid;}else{end = mid;}}return Math.min(nums[start],nums[end]);}
}

88. 合并两个有序数组

注意：此题是nums1后面有为空的情况，所以采用的是倒序进比较然后放入数组中。

对于数组的操作，必须保证不能越界，不能写成while(l>=0 || r >=0) ,然后按照这种逻辑去，因为他可能会出现数组的边界越界的情况。

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int l =m-1,r = n-1,i = m + n - 1 ;while(l >=0 && r >= 0){if(nums1[l] < nums2[r]){nums1[i--] = nums2[r--]; }else {nums1[i--] =nums1[l--];}}while(l >=0){nums1[i--] = nums1[l--];}while(r >= 0){nums1[i--] = nums2[r--];}}}

4. 寻找两个有序数组的中位数—(很重要)

对于一个长度为n的已排序数列a，若n为奇数，中位数为第(n / 2 + 1) 的数, 若n为偶数，则中位数(a[n / 2] + a[n / 2 + 1]) / 2如果我们可以在两个数列中求出第K小的元素，便可以解决该问题不妨设数列A元素个数为n，数列B元素个数为m，各自升序排序，求第k小元素取A[k / 2] B[k / 2] 比较，如果 A[k / 2] > B[k / 2] 那么，所求的元素必然不在B的前k / 2个元素中(证明反证法)反之，必然不在A的前k / 2个元素中，于是我们可以将A或B数列的前k / 2元素删去，求剩下两个数列的k - k / 2小元素，于是得到了数据规模变小的同类问题，递归解决如果 k / 2 大于某数列个数，所求元素必然不在另一数列的前k / 2个元素中，同上操作就好。

注意：索引=第K个数（前k个数）-1
2.注意：必须除以2.0而不是2；

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int n = nums1.length+ nums2.length;if(n%2==0){  //如果是偶数return (findKth(nums1,0,nums2,0,n/2)+ findKth(nums1,0,nums2,0,n/2+1))/2.0;}return findKth(nums1,0,nums2,0,n/2+1);//如果是奇数}public int findKth(int[] nums1,int i1,int[] nums2,int i2,int k){if(i1 >= nums1.length){return nums2[i2 + k - 1];}if(i2 >= nums2.length){return nums1[i1 + k - 1];}//这里主要是：如果等于1了的话，k/2 =0，那么下面就会出错if(k == 1){return Math.min(nums1[i1 + k -1],nums2[i2 + k - 1]);}int halfKthOfA= i1 +k/2-1 <nums1.length?nums1[i1+k/2-1]:Integer.MAX_VALUE;int halfKthOfB= i2 +k/2-1 <nums2.length?nums2[i2+k/2-1]:Integer.MAX_VALUE;if(halfKthOfA <  halfKthOfB){return findKth(nums1,i1+k/2,nums2,i2,k-k/2);}else{return findKth(nums1,i1,nums2,i2+k/2,k-k/2);}}
}

189. 旋转数组

思路：使用3步翻转法，首先翻转整个数组，然后在前k个翻转，剩余的在进行翻转。
特别注意：k%=n； 这里特别容易遗忘(有可能k的长度超过了nums的长度)

• 整个数组翻转
• 前K个翻转
• 后面剩余的在进行饭庄

(2)向 右移动的话需要进行 K%=n；

注意：索引=第K个数（前k个数）-1

class Solution {public void rotate(int[] nums, int k) {k %= nums.length;reverse(nums,0,nums.length-1);reverse(nums,0,k-1);reverse(nums,k,nums.length-1);}public void reverse(int[] nums,int start,int end){while(start < end){int temp = nums[start];nums[start] = nums[end];nums[end] = temp;start++;end--;}}
}