二分查找/排序：二分查找-I、二维数组中的查找、寻找峰值、数组中的逆序对、旋转数组的最小数字、比较版本号
目录
一、二分查找-I
1.1 题目
1.2 题解
思路：由于数组中元素是升序排列的，因此可将target与数组的中间位置的元素比较
如果target>arr[mid],说明要找的target一定在数组的后半段区间，
如果target<arr[mid]，说明要找的target一定在数组的前半段区间，
如果arr[mid]==target，说明找到了,返回mid
而在前半段或后半段区间查找target，又可以按照与中间值比较的方法，如此的循环下去，直到找到target对应的下标或区间的左右端相遇，退出循环
代码：
public int search (int[] nums, int target) {
int l=0;
int r=nums.length-1;
while(l<=r){
int mid=(l+r)/2;
if(nums[mid]==target){
return mid;
}else if(target>nums[mid]){
l=mid+1;
}else {
r=mid-1;
}
}
return -1;
}
二、二维数组中的查找
2.1 题目
2.2 题解
查找的本质其实是在排除
思路：将二维数组的右上角作为查找的其实位置，比较target和该位置的元素
右上角的元素特点是，所处行的最大值，所处列的最小值
（1）如果target>右上角的元素，向下移动一行
（2）如果target<右上角的元素，向左移动一列
（3）如果target==右上角的元素，返回该位置即可
代码：
public boolean Find(int target, int [][] array) {
int i=0;
int j=array[0].length-1;
while(i<array.length && j>=0){
if(target==array[i][j]){
return true;
}else if(target>array[i][j]){
i++;
}else {
j--;
}
}
return false;
}
三、寻找峰值
3.1 题目
3.2 题解
题目分析：边界位置视为最小值，因此不断的往高处走，一定会遇到波峰
思路：判断中间位置的元素和其右侧相邻的元素大小，如果中间位置的元素较小，说明往右半区间走是存在上坡的，如果间位置的元素较小，说明往左半区间走是存在上坡的
代码：
public int findPeakElement (int[] nums) {
int l=0;
int r=nums.length-1;
while(l<r){
int mid=(l+r)/2;
if(nums[mid]<nums[mid+1]){
//此时能确定mid位置一定不是波峰，因此可以掠过此位置
l=mid+1;
}else {
//这里不能写成 r=mid-1，因为有可能mid位置就是波峰，不能掠过该位置
r=mid;
}
}
return l;
}
四、数组中的逆序对
4.1 题目
4.2 题解
思路：归并排序，在归并的过程中统计逆序对的个数
代码：
public class Solution {
private int count = 0;
public int InversePairs(int [] array) {
if (array == null || array.length < 2)return 0;
mergeSort(0, array.length - 1, array);
return count;
}
public void mergeSort(int left, int right, int[] array) {
if (left >= right) return ;
int mid = (left + right) / 2;
mergeSort(left, mid, array);
mergeSort(mid + 1, right, array);
merge(left, mid, right, array);
}
public void merge(int left, int mid, int right, int[] array) {
int[] tmp = new int[right - left + 1];
int k = 0;
int i = left;
int j = mid + 1;
while (i <= mid && j <= right) {
if (array[i] <= array[j]) {
tmp[k] = array[i];
i++;
k++;
} else {
tmp[k] = array[j];
count += (mid - i + 1);
count %= 1000000007;
j++;
k++;
}
}
while (i <= mid) {
tmp[k++] = array[i++];
}
while (j <= right) {
tmp[k++] = array[j++];
}
for (int num : tmp) {
array[left++] = num;
}
}
}
五、旋转数组的最小数字
5.1 题目
5.2 题解
思路：二分法，因为旋转数组是由一个有序数组旋转得到的，因此旋转数组可分为左排序数组和右排序数组两个部分，在这两个排序数组中元素都是有序的且左排序数组中的值都比右排序数组中的值大，因此右排序数组中的第一个数就是最小的，我们要做的是通过比较数组中间位置的值和最右侧元素值的大小，找到右排序数组中的第一个数
代码：
public int minNumberInRotateArray(int [] array) {
int l=0;
int r=array.length-1;
while(l<r){
int mid=(l+r)/2;
if(array[mid]>array[r]){
l=mid+1;
}else if(array[mid]<array[r]){
r=mid;
}else {
r--;
}
}
return array[l];
}
六、比较版本号
6.1 题目
6.2 题解
思路：使用两个指针分别用来遍历两个字符串，再遍历的过程中将每个修定号都转成整数(方便直接比较大小)，两个指针都是遇到 . 停止，如果比较当前的修订号大小，如果不相等就返回结果，相等就继续用同样的方式比较下一个修订号
具体步骤：
step1：i，j分别用来遍历两个字符串
step2：i，j遍历遇到 . 停止，说明遍历完一个修订号了，比较当前二者的修订号，如果相等就继续比较，如果不相等就返回相应的结果
代码：
public int compare (String version1, String version2) {
int n1 = version1.length();
int n2 = version2.length();
int i = 0;
int j = 0;
//注意这里是 || 而不是&& ，因为其中一个字符串遍历到结尾，不能停止比较，会默认该字符串后面的版本号都为0，直到比较出两个版本号的大小
while (i < n1 || j < n2) {
long num1 = 0;
while (i < n1 && version1.charAt(i) != '.') {
num1 = num1 * 10 + (version1.charAt(i) - '0');
i++;
}
i++;
long num2 = 0;
while (j < n2 && version2.charAt(j) != '.') {
num2 = num2 * 10 + (version2.charAt(j) - '0');
j++;
}
j++;
if (num1 > num2) {
return 1;
}
if (num1 < num2) {
return -1;
}
}
return 0;
}