1轧邪、二分查找
給定一個 元素升序的刽脖、無重復(fù)數(shù)字的整型數(shù)組 nums 和一個目標(biāo)值 target ，寫一個函數(shù)搜索 nums 中的 target忌愚，如果目標(biāo)值存在返回下標(biāo)（下標(biāo)從 0 開始）曲管，否則返回 -1

    public int search (int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        //從首尾邊界開始直到二者相遇
        while(l <= r){ 
            //每次檢查的中點(diǎn)值
            // int m = l + (l - r);
            int m = (l + r) / 2; 
            if(nums[m] == target)
                return m;
            //目標(biāo)值小于中間值，目標(biāo)值一定在左區(qū)間硕糊，縮小右邊界
            if(nums[m] > target) 
                r = m - 1;
            //目標(biāo)值大于中間值院水，目標(biāo)值一定在右區(qū)間，縮小左邊界
            else 
                l = m + 1;
        }
        //未找到
        return -1; 
    }

解析：
劃分左右區(qū)間简十，使目標(biāo)值和中間值進(jìn)行比較檬某，從而判斷目標(biāo)值在哪個區(qū)間內(nèi)，然后縮小區(qū)間繼續(xù)劃分重復(fù)操作直到找到目標(biāo)值

2螟蝙、二維數(shù)組中的查找
二維數(shù)組array中（每個一維數(shù)組的長度相同）恢恼，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序胰默。請完成一個函數(shù)场斑，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)

方法一：暴力搜索

public boolean Search(int[][] arr,int target){
    row=arr.length;
    //總列數(shù) 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;
}

解析：按照從上到下從左到右依次搜索初坠，直到找到目標(biāo)值

方法二：線性搜索

    public boolean Find(int target, int [][] array) {
        //優(yōu)先判斷特殊
        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;
    }
}

解析：
因為此二維數(shù)組是行列遞增碟刺，所以每一行的最后一位數(shù)字大于前面所有锁保，每一列最后一位大于前面所有。將搜索起始位置設(shè)定在矩陣的右上角或者左下角半沽，當(dāng)起始為左下角時爽柒，若元素較大則往上走；元素較小則往右走者填，直到找到目標(biāo)值

方法三：二分搜索

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;
}

利用二分搜索浩村，從上到下每一行依次進(jìn)行二分搜索，直到找到目標(biāo)值

3占哟、尋找峰值
給定一個長度為n的數(shù)組nums心墅，請你找到峰值并返回其索引酿矢。數(shù)組可能包含多個峰值，在這種情況下怎燥，返回任何一個所在位置即可

若數(shù)組相鄰元素不相等瘫筐，那么就有且僅有以上四種情況，每種情況都存在峰值

    import java.util.*;
public class Solution {
    public int findPeakElement (int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        //二分法
        while(left < right){ 
            //防止直接相加發(fā)生溢出
            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]說明在“下坡”之众，則應(yīng)該使right = mid（mid可能是峰值），往“峰”處壓縮

4依许、尋找數(shù)組中的逆序?qū)?br> 方法一：暴力解法

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;
    }
}

解析：
選擇排序的方式使當(dāng)前元素與其后面的元素依次進(jìn)行比較

方法二：歸并統(tǒng)計

public class Solution {
    int count = 0;
    public int InversePairs(int [] array) {
        // 長度小于2則無逆序?qū)?        if(array.length < 2)
            return 0;
        // 進(jìn)入歸并
        mergeSort(array,0,array.length-1);
        return count;
    }

    public void mergeSort(int[] array,int left,int right){
        // 找分割點(diǎn)
        int mid = left+(right-left)/2;
        if(left < right){
            // 左子數(shù)組
            mergeSort(array,left,mid);
            // 右子數(shù)組
            mergeSort(array,mid+1,right);
            // 并
            merge(array,left,mid,right);
        }
    }

    public void merge(int[] array,int left,int mid,int right){
        // 創(chuàng)建臨時數(shù)組棺禾，長度為此時兩個子數(shù)組加起來的長度
        int[] arr =  new int[right-left+1];
        // 臨時數(shù)組的下標(biāo)起點(diǎn)
        int c = 0;
        // 保存在原數(shù)組的起點(diǎn)下標(biāo)值
        int s = left;
        // 左子數(shù)組的起始指針
        int l = left;
        // 右子數(shù)組的起始指針
        int r = mid+1;
        while(l <= mid && r <= right ){
            // 當(dāng)左子數(shù)組的當(dāng)前元素小的時候，跳過悍手，無逆序?qū)?            if(array[l] <= array[r]){
                // 放入臨時數(shù)組
                arr[c] = array[l];
                // 臨時數(shù)組下標(biāo)+1
                c++;
                // 左子數(shù)組指針右移
                l++;
            }else{ // 否則帘睦，此時存在逆序?qū)?                // 放入臨時數(shù)組
                arr[c] = array[r];
                // 逆序?qū)Φ膫€數(shù)為    左子數(shù)組的終點(diǎn)- 當(dāng)前左子數(shù)組的當(dāng)前指針+1
                count += mid-l+1;
                count %= 1000000007;
                // 臨時數(shù)組+1
                c++;
                // 右子數(shù)組的指針右移
                r++;
            }
        }

        // 左子數(shù)組還有元素時袍患，全部放入臨時數(shù)組
        while(l <= mid)
            arr[c++] = array[l++];
        // 右子數(shù)組還有元素時坦康，全部放入臨時數(shù)組
        while(r <= right)
            arr[c++] = array[r++];
        // 將臨時數(shù)組中的元素放入到原數(shù)組的指定位置
        for(int num:arr){
            array[s++] = num;
        }
    }
}

解析：
利用歸并排序，在合并的時候會進(jìn)行比較判斷诡延，若左邊元素小于右邊元素則算作逆序?qū)Α?br> 在合并 {4 ,5} {1 , 2} 的時候滞欠，首先我們判斷 1 < 4，我們即可統(tǒng)計出逆序?qū)?肆良，為什么呢筛璧？這利用了數(shù)組的部分有序性。因為我們知道 {4 ,5} 這個數(shù)組必然是有序的惹恃，因為是合并上來的夭谤。此時當(dāng) 1比4小的時候，證明4以后的數(shù)也都比1大巫糙，此時就構(gòu)成了從4開始到 {4,5}這個數(shù)組結(jié)束朗儒，這么多個逆序?qū)Γ?個），此時利用一個臨時數(shù)組参淹，將1存放起來醉锄，接著比較2和4的大小，同樣可以得到有2個逆序?qū)φ阒担谑菍?也放進(jìn)臨時數(shù)組中恳不，此時右邊數(shù)組已經(jīng)完全沒有元素了，則將左邊剩余的元素全部放進(jìn)臨時元素中开呐，最后將臨時數(shù)組中的元素放進(jìn)原數(shù)組對應(yīng)的位置烟勋。

5规求、旋轉(zhuǎn)數(shù)組的最小數(shù)字
有一個長度為 n 的非降序數(shù)組，比如[1,2,3,4,5]卵惦，將它進(jìn)行旋轉(zhuǎn)颓哮，即把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，變成一個旋轉(zhuǎn)數(shù)組鸵荠，比如變成了[3,4,5,1,2]冕茅，或者[4,5,1,2,3]這樣的。請問蛹找，給定這樣一個旋轉(zhuǎn)數(shù)組姨伤，求數(shù)組中的最小值

方法一：暴力搜索

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;
}

解析：
從前向后遍歷找出最小數(shù)字

方法二：二分法

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;
        //若區(qū)間中點(diǎn)值小于區(qū)間右界值，最小值一定在中點(diǎn)左邊
        }else if(arr[mid]<arr[right]){
            right=mid;
        }else{
            // right=right-1;
            right--;
        }
    }
}

解析：
旋轉(zhuǎn)后無序的點(diǎn)就是最小的數(shù)字庸疾，
1乍楚、若區(qū)間中點(diǎn)值大于區(qū)間右界值，最小值一定在中點(diǎn)右邊
2届慈、若區(qū)間中點(diǎn)值小于區(qū)間右界值徒溪，最小值一定在中點(diǎn)左邊
3、若區(qū)間中點(diǎn)值等于區(qū)間右界值金顿，無法判斷臊泌，逐個縮小右界

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]每一輪都以數(shù)組中第一個數(shù)作為軸點(diǎn)
2渠概、while(i<j && arr[j]>=pivot) j--從最左開始每個數(shù)依次和軸點(diǎn)進(jìn)行比較，要求左邊所有數(shù)只要大于軸點(diǎn)就準(zhǔn)備進(jìn)行交換
3嫂拴、while(i<j && arr[i]<=pivot) i++從最右開始每個數(shù)依次和軸點(diǎn)進(jìn)行比較播揪，要求右邊所有數(shù)只要小于軸點(diǎn)就準(zhǔn)備進(jìn)行交換
4、swap(arr,i,j)左右進(jìn)行交換筒狠，swap(arr,left,j)軸點(diǎn)歸位
5猪狈、quickSort(arr,left,j-1)、quickSort(arr,j+1,right)循環(huán)遞歸辩恼，快速排序的每一輪處理其實就是將這一輪的軸點(diǎn)歸位雇庙，直到所有的數(shù)都?xì)w位為止