1、二分查找
给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1
public int search (int[] nums, int target) {
int l = 0;
int r = nums.length - 1;
//从首尾边界开始直到二者相遇
while(l <= r){
//每次检查的中点值
// int m = l + (l - r);
int m = (l + r) / 2;
if(nums[m] == target)
return m;
//目标值小于中间值，目标值一定在左区间，缩小右边界
if(nums[m] > target)
r = m - 1;
//目标值大于中间值，目标值一定在右区间，缩小左边界
else
l = m + 1;
}
//未找到
return -1;
}
解析：
划分左右区间，使目标值和中间值进行比较，从而判断目标值在哪个区间内，然后缩小区间继续划分重复操作直到找到目标值
2、二维数组中的查找
二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数
方法一：暴力搜索
public boolean Search(int[][] arr,int target){
row=arr.length;
//总列数 arr[行][列]
col=arr[0].length;
for (int i=0;i<row;i++) {
for (int j=0;j<col;j++) {
if(arr[i]][j]==target){
return true;
}
}
}
return false;
}
解析：按照从上到下从左到右依次搜索，直到找到目标值
方法二：线性搜索
public boolean Find(int target, int [][] array) {
//优先判断特殊
if(array.length == 0)
return false;
int n = array.length;
if(array[0].length == 0)
return false;
int m = array[0].length;
//从最左下角的元素开始往左或往上
for(int i = n - 1, j = 0; i >= 0 && j < m; ){
//元素较大，往上走
if(array[i][j] > target)
i--;
//元素较小，往右走
else if(array[i][j] < target)
j++;
else
return true;
}
return false;
}
}
解析：
因为此二维数组是行列递增，所以每一行的最后一位数字大于前面所有，每一列最后一位大于前面所有。将搜索起始位置设定在矩阵的右上角或者左下角，当起始为左下角时，若元素较大则往上走；元素较小则往右走，直到找到目标值
方法三：二分搜索
public boolean binarySearch(int[][] array) {
for (int i = 0; i < m; i++) {
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (array[i][mid] == target) {
return true;
} else if (array[i][mid] < target) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return false;
}
利用二分搜索，从上到下每一行依次进行二分搜索，直到找到目标值
3、寻找峰值
给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可
若数组相邻元素不相等，那么就有且仅有以上四种情况，每种情况都存在峰值
import java.util.*;
public class Solution {
public int findPeakElement (int[] nums) {
int left = 0;
int right = nums.length - 1;
//二分法
while(left < right){
//防止直接相加发生溢出
int mid = ((right - left) >> 1) + left;
//右边是往下，不一定有坡峰
if(nums[mid] > nums[mid + 1])
right = mid;
//右边是往上，一定能找到波峰
else
left = mid + 1;
}
//其中一个波峰
return right;
}
}
解析：
nums[mid] < nums[mid + 1]说明在“上坡”，则可以使left = mid + 1（mid肯定不是峰值），向“峰”处压缩
nums[mid] > nums[mid + 1]说明在“下坡”，则应该使right = mid（mid可能是峰值），往“峰”处压缩
4、寻找数组中的逆序对
方法一：暴力解法
public class Solution {
public int InversePairs(int[] array) {
int cnt = 0;
int len = array.length;
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
if (array[i] > array[j]) {
cnt++;
}
}
}
return cnt;
}
}
解析：
选择排序的方式使当前元素与其后面的元素依次进行比较
方法二：归并统计
public class Solution {
int count = 0;
public int InversePairs(int [] array) {
// 长度小于2则无逆序对
if(array.length < 2)
return 0;
// 进入归并
mergeSort(array,0,array.length-1);
return count;
}
public void mergeSort(int[] array,int left,int right){
// 找分割点
int mid = left+(right-left)/2;
if(left < right){
// 左子数组
mergeSort(array,left,mid);
// 右子数组
mergeSort(array,mid+1,right);
// 并
merge(array,left,mid,right);
}
}
public void merge(int[] array,int left,int mid,int right){
// 创建临时数组，长度为此时两个子数组加起来的长度
int[] arr = new int[right-left+1];
// 临时数组的下标起点
int c = 0;
// 保存在原数组的起点下标值
int s = left;
// 左子数组的起始指针
int l = left;
// 右子数组的起始指针
int r = mid+1;
while(l <= mid && r <= right ){
// 当左子数组的当前元素小的时候，跳过，无逆序对
if(array[l] <= array[r]){
// 放入临时数组
arr[c] = array[l];
// 临时数组下标+1
c++;
// 左子数组指针右移
l++;
}else{ // 否则，此时存在逆序对
// 放入临时数组
arr[c] = array[r];
// 逆序对的个数为 左子数组的终点- 当前左子数组的当前指针+1
count += mid-l+1;
count %= 1000000007;
// 临时数组+1
c++;
// 右子数组的指针右移
r++;
}
}
// 左子数组还有元素时，全部放入临时数组
while(l <= mid)
arr[c++] = array[l++];
// 右子数组还有元素时，全部放入临时数组
while(r <= right)
arr[c++] = array[r++];
// 将临时数组中的元素放入到原数组的指定位置
for(int num:arr){
array[s++] = num;
}
}
}
解析：
利用归并排序，在合并的时候会进行比较判断，若左边元素小于右边元素则算作逆序对。
在合并 {4 ,5} {1 , 2} 的时候，首先我们判断 1 < 4，我们即可统计出逆序对为2，为什么呢？这利用了数组的部分有序性。因为我们知道 {4 ,5} 这个数组必然是有序的，因为是合并上来的。此时当 1比4小的时候，证明4以后的数也都比1大，此时就构成了从4开始到 {4,5}这个数组结束，这么多个逆序对（2个），此时利用一个临时数组，将1存放起来，接着比较2和4的大小，同样可以得到有2个逆序对，于是将2也放进临时数组中，此时右边数组已经完全没有元素了，则将左边剩余的元素全部放进临时元素中，最后将临时数组中的元素放进原数组对应的位置。
5、旋转数组的最小数字
有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值
方法一：暴力搜索
public int minNumberInRotateArray(int[] arr){
if(arr.length<=0) return null;
int res=arr[0];
for(int i=1;i<arr.length;i++) {
int res=math.min(arr[i],res);
}
return res;
}
解析：
从前向后遍历找出最小数字
方法二：二分法
public min minNumberInRotateArray(int[] arr){
int left=0;
int right=arr.length-1;
while(left<right){
int mid=(left+right)/2;
if(arr[mid]>arr[right]){
left=mid+1;
//若区间中点值小于区间右界值，最小值一定在中点左边
}else if(arr[mid]<arr[right]){
right=mid;
}else{
// right=right-1;
right--;
}
}
}
解析：
旋转后无序的点就是最小的数字，
1、若区间中点值大于区间右界值，最小值一定在中点右边
2、若区间中点值小于区间右界值，最小值一定在中点左边
3、若区间中点值等于区间右界值，无法判断，逐个缩小右界
6、快速排序
public class QuickSort{
public static void main(String[] args) {
int[] nums={7,4,5,2,8,0,11};
System.out.println(Arrays.toString(nums));
quickSort(nums,0,nums.length-1);
System.out.println(Arrays.toString(nums));
}
public static void quickSort(int[] arr,int left,int right){
if(left>right) return;
int i,j,pivot;
i=left;
j=right;
pivot=arr[left];
while(i<j){
while(i<j && arr[j]>=pivot) j--;
while(i<j && arr[i]<=pivot) i++;
if(i<j){
swap(arr,i,j);
}
}
swap(arr,left,j);
quickSort(arr,left,j-1);
quickSort(arr,j+1,right);
}
public static void swap(int[] arr,int left,int right){
int temp=arr[left];
arr[left]=arr[right];
arr[right]=temp;
}
}
解析：
1、pivot=arr[left]每一轮都以数组中第一个数作为轴点
2、while(i<j && arr[j]>=pivot) j--从最左开始每个数依次和轴点进行比较，要求左边所有数只要大于轴点就准备进行交换
3、while(i<j && arr[i]<=pivot) i++从最右开始每个数依次和轴点进行比较，要求右边所有数只要小于轴点就准备进行交换
4、swap(arr,i,j)左右进行交换，swap(arr,left,j)轴点归位
5、quickSort(arr,left,j-1)、quickSort(arr,j+1,right)循环递归，快速排序的每一轮处理其实就是将这一轮的轴点归位，直到所有的数都归位为止
