面试 TOP101 二分查找/排序专题题解汇总Java版（BM17 —— BM22）

刷题挑战链接

二分查找/排序

题号	题目名称	核心思路	时间复杂度	空间复杂度	代码亮点	牛客原题链接
BM17	二分查找-I	二分查找，不断缩小搜索范围	O(logn)	O(1)	使用位运算优化中点计算，逻辑清晰	🔗 直达
BM18	二维数组中的查找	从左下角或右上角开始查找，利用二维数组的有序性	O(m+n)	O(1)	选择合适的起点，避免重复比较，逻辑简洁	🔗 直达
BM19	寻找峰值	二分查找，利用峰值的性质	O(logn)	O(1)	使用二分查找快速定位峰值，逻辑清晰	🔗 直达
BM20	数组中的逆序对	归并排序，在合并过程中统计逆序对	O(nlogn)	O(n)	使用归并排序优化逆序对统计，逻辑简洁	🔗 直达
BM21	旋转数组的最小数字	二分查找，利用旋转数组的性质	O(logn)	O(1)	使用二分查找快速定位最小值，逻辑清晰	🔗 直达
BM22	比较版本号	按点分隔版本号，逐段比较	O(n)	O(1)	逐段比较版本号，逻辑简洁	🔗 直达

✅ 建议复习顺序（由易到难）：

BM17 → BM18 → BM19 → BM21 → BM20 → BM22

BM17 二分查找-I

二分查找-I_牛客题霸_牛客网
https://www.nowcoder.com/practice/d3df40bd23594118b57554129cadf47b?tpId=295&tqId=1499549&sourceUrl=%2Fexam%2Foj

import java.util.*;
public class Solution {public int search (int[] nums, int target) {int l = 0;// 1. 定义左端点int r = nums.length - 1;// 2. 定义右端点while(l <= r){int mid = (l + r) >> 1;// 3. 二分找中点if(nums[mid] == target) return mid;// 4. 判断中点值是否是targetelse if(nums[mid] > target) r = mid - 1;// 5. 中点值大于目标值 区间左移else l = mid + 1;// 6. 反之区间右移}return -1;// 7. 二分完毕没找到}
}

BM18 二维数组中的查找

二维数组中的查找_牛客题霸_牛客网
https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

public class Solution {public boolean Find(int target, int [][] array) {if (array.length == 0) return false;          // 1. 数组为空，直接返回 falseint n = array.length;                         // 2. 获取数组行数if (array[0].length == 0) return false;       // 3. 首行长度为 0，说明列数为 0，返回 falseint m = array[0].length;                      // 4. 获取数组列数// 5. 从左下角 (n-1,0) 开始查找：往上值变小，往右值变大for (int i = n - 1, j = 0; i >= 0 && j < m; ) {if (array[i][j] > target) i--;            // 6. 当前值大于目标，上移一行else if (array[i][j] < target) j++;       // 7. 当前值小于目标，右移一列else return true;                         // 8. 找到目标，返回 true}return false;                                 // 9. 遍历结束仍未找到，返回 false}
}

BM19 寻找峰值

寻找峰值_牛客题霸_牛客网
https://www.nowcoder.com/practice/fcf87540c4f347bcb4cf720b5b350c76?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

public class Solution {public boolean Find(int target, int [][] array) {if (array.length == 0) return false;          // 1. 数组为空，直接返回 falseint n = array.length;                         // 2. 获取数组行数if (array[0].length == 0) return false;       // 3. 首行长度为 0，说明列数为 0，返回 falseint m = array[0].length;                      // 4. 获取数组列数// 5. 从左下角 (n-1,0) 开始查找：往上值变小，往右值变大for (int i = n - 1, j = 0; i >= 0 && j < m; ) {if (array[i][j] > target) i--;            // 6. 当前值大于目标，上移一行else if (array[i][j] < target) j++;       // 7. 当前值小于目标，右移一列else return true;                         // 8. 找到目标，返回 true}return false;                                 // 9. 遍历结束仍未找到，返回 false}
}

BM20 数组中的逆序对

数组中的逆序对_牛客题霸_牛客网
https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

public class Solution {public int mod = 1000000007; // 1. 定义模数，用于防止结果溢出public int mergeSort(int left, int right, int[] data, int[] temp) {if (left >= right) return 0; // 2. 如果区间长度小于等于1，无需排序，返回0int mid = (left + right) / 2; // 3. 计算中间位置，将数组分为两部分// 4. 递归计算左半部分和右半部分的逆序对数量int res = mergeSort(left, mid, data, temp) + mergeSort(mid + 1, right, data, temp);res %= mod; // 5. 对结果取模，防止溢出int i = left, j = mid + 1; // 6. 初始化左右两部分的指针// 7. 将原数组的值复制到临时数组，用于归并for (int k = left; k <= right; k++) temp[k] = data[k];// 8. 归并排序并统计逆序对for (int k = left; k <= right; k++) {if (i == mid + 1) data[k] = temp[j++]; // 9. 左半部分已处理完，直接取右半部分的值else if (j == right + 1 || temp[i] <= temp[j]) data[k] = temp[i++]; // 10. 右半部分已处理完或左半部分的值小于等于右半部分的值else { data[k] = temp[j++]; // 11. 右半部分的值小于左半部分的值，发生逆序res += mid - i + 1; // 12. 计算逆序对数量：左半部分剩余的元素个数}}return res % mod; // 13. 返回当前区间内的逆序对总数}public int InversePairs(int[] array) {int n = array.length; // 14. 获取数组长度int[] res = new int[n]; // 15. 创建临时数组用于归并排序return mergeSort(0, n - 1, array, res); // 16. 调用归并排序函数计算逆序对}
}

BM21 旋转数组的最小数字

旋转数组的最小数字_牛客题霸_牛客网
https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=295&tqId=23269&sourceUrl=%2Fexam%2Foj

1. 暴力 + Stream流

import java.util.*;public class Solution {// 1. 找到旋转数组中的最小值public int minNumberInRotateArray(int[] nums) {// 2. 使用 Java 8 的 Stream API 找到数组中的最小值return Arrays.stream(nums).min().getAsInt();}
}

2. 二分

import java.util.*;public class Solution {public int minNumberInRotateArray (int[] nums) {if(nums.length == 0) return 0; // 1. 如果数组为空，返回 0int l = 0; // 2. 初始化左指针int r = nums.length - 1; // 3. 初始化右指针while(l < r){ // 4. 当左指针小于右指针时，继续查找int mid = (l + r) / 2; // 5. 计算中间位置if(nums[mid] < nums[r]) r = mid; // 6. 如果中间值小于右端值，最小值在左半部分或中间值就是最小值else if(nums[mid] > nums[r]) l = mid + 1; // 7. 如果中间值大于右端值，最小值在右半部分else r --; // 8. 如果中间值等于右端值，无法确定最小值位置，右指针左移}return nums[l]; // 9. 返回最小值}
}

BM22 比较版本号

比较版本号_牛客题霸_牛客网
https://www.nowcoder.com/practice/2b317e02f14247a49ffdbdba315459e7?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

import java.util.*;public class Solution {public int compare(String v1, String v2) {int n1 = v1.length(); // 1. 获取版本号 v1 的长度int n2 = v2.length(); // 2. 获取版本号 v2 的长度int i = 0, j = 0; // 3. 初始化两个指针，分别指向 v1 和 v2 的起始位置while (i < n1 || j < n2) { // 4. 当两个指针都未超出各自版本号的长度时，继续比较long num1 = 0; // 5. 初始化 v1 的当前部分数字long num2 = 0; // 6. 初始化 v2 的当前部分数字// 7. 解析 v1 的当前部分数字while (i < n1 && v1.charAt(i) != '.') {num1 = num1 * 10 + (v1.charAt(i) - '0'); // 8. 将字符转换为数字并累加i++;}i++; // 9. 跳过点（`.`）// 10. 解析 v2 的当前部分数字while (j < n2 && v2.charAt(j) != '.') {num2 = num2 * 10 + (v2.charAt(j) - '0'); // 11. 将字符转换为数字并累加j++;}j++; // 12. 跳过点（`.`）// 13. 比较当前部分数字if (num1 > num2) return 1; // 14. 如果 v1 的当前部分大于 v2 的当前部分，返回 1else if (num1 < num2) return -1; // 15. 如果 v1 的当前部分小于 v2 的当前部分，返回 -1}return 0; // 16. 如果所有部分都相等，返回 0}
}