排序模板 & 二叉树遍历模板 & 二分模板

排序

这里只简单的放上相应的模板，具体的算法思想见我另外一篇文章 《十大内部排序》

细节

分类

复杂度

补充：

在这里要说明的是，这个图里的快排空间复杂度错了，快排的平均空间复杂度应该是 O(logn)，就是栈的深度，但是最差的情况下，比如全是倒序，则空间复杂度为栈深度 O(n)。归并排序每次递归需要用到一个辅助表，长度与待排序的表相等，虽然递归次数是O(log2n)，但每次递归都会释放掉所占的辅助空间，所以下次递归的栈空间和辅助空间与这部分释放的空间就不相关了，因而空间复杂度还是 O(n)。

稳定性

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
• 不稳定排序算法：谐音记忆法：快（快排） 些（希尔）选（选择）对（堆）。
• 总共4个不稳定，6个稳定。

面试点

jdk层面实现的sort总共是两类，一个是 Arrays.sort()， Collections.sort()：

1. Arrays.sort()

   • 如果数组内元素是基本数据类型，最主要采用的是双轴快速排序「其实就是三路快排一模一样的思路，只不过三路快排中间是 = pivot1，而双轴快速排序是（pivot1，pivot2），具体戳链接：https://www.cnblogs.com/nullzx/p/5880191.html 。

   • 总结一下：数组长度小于47的时候是用直接插入算法，大于47并且小于286是采用双轴快速排序，大于286如果连续性好「也就是元素大多有序，有一个flag专门用来记录数组元素的升降次数，代表这个数组的连续性」采用的是归并排序，否则还是依旧采用双轴快速排序。

   • 如果数组内元素是对象，采用的是TimSort.sort()，跟 Collections.sort()一样，都是采用的这个函数，这是归并排序算法和插入排序的结合。

2. Collections.sort()，采用 TimSort.sort()。

TimSort.sort() 大概原理：

1. 当待排序元素小于32个时，采用二分插入排序，是插入排序的一种改进，可以减少插入排序比较的次数。当找到插入位置时，直接利用System.copy()函数即可。
2. 当待排序元素大于等于32个时，进行归并排序（和传统的归并不一样），首先将排序元素分区，每个分区的大小区间为[16,32)，然后依次对每个分区进行排序（具体实现依然是二分插入排序），排完序的分区压入栈（准确的说不是栈，而是一个数组，用来记录排序好的分区），当栈内的分区数满足条件时，进行分区合并，合并为一个更大的分区，当栈中只剩一个分区时，排序完成。

模板

交换排序之冒泡

public class BubbleSort {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int len = scanner.nextInt();
        System.out.println("要输入的数字的个数：" + len);
        int[] nums = new int[len];
        for(int i = 0;i < len;i++){
            nums[i] = scanner.nextInt();
        }
        Bubble(nums);
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 注意点：外循环是 n - 1 次，所以可以 i 从 1 开始取
     * 内循环是从 0 到 n - i // 这个貌似是最容易忘记的
     * 比较的是 j 和 j+1
     * @param nums
     */
    public static void Bubble(int[] nums){
        for(int i = 1;i < nums.length;i++){
            boolean flag = true;
            for(int j = 0;j < nums.length - i;j++){
                if(nums[j] > nums[j+1]){
                    swap(nums,j,j+1);
                    flag = false;
                }
            }
            if(flag) return;
        }
    }

    private static void swap(int[] nums, int j, int i) {
        int temp = nums[j];
        nums[j] = nums[i];
        nums[i] = temp;
    }
}

交换排序之快排

public static void main(String[] args) {
      Scanner scanner = new Scanner(System.in);
      System.out.print("请输入数组的大小： ");
      int len = scanner.nextInt();
      int[] nums = new int[len];
      for (int i = 0;i < len;i++){
          nums[i] = scanner.nextInt();
      }
      quick(nums,0,len-1);
      System.out.println(Arrays.toString(nums));

  }
public static void quick(int[] nums,int left,int right){
      if(left < right){
          int partition = partition(nums,left,right);
          quick(nums,left,partition-1);
          quick(nums,partition+1,right);
      }

  }

  private static int partition(int[] nums, int left, int right) {
      // 基准值
      // 优化，就是尽量能做到分治，也就是选取的基准值尽量在中间是性能最好的
      int mid = (left + right)/2;
      dealPivot(nums,left,mid,right);
      int pivot = left;
      // 定义两个指针
      int p = left;
      int q = right;
      while(p < q){
          while(p < q && nums[q] >= nums[pivot]){
              q--;
          }
          while(p < q && nums[p] <= nums[pivot]){
              p++;
          }
          swap(nums,p,q);
      }
      swap(nums,p,pivot);
      return p;
  }

  private static void dealPivot(int[] nums, int left, int mid, int right) {
      if((left - mid) * (mid - right) > 0){  // left < mid < right
          swap(nums,left,mid);
          return;
      }
      else if((mid - left) * (left - right) > 0){ // left 是中间值
          swap(nums,left,right);
          return;
      }
      return;
  }

交换排序之三路快排

private static void quickSortByThreeWays(int[] nums, int left, int right) {
        if(left < right){
            int[] par = quickThreePartition(nums,left,right);
            int lt = par[0];
            int gt = par[1];
            quickSortByThreeWays(nums,left,lt-1);
            quickSortByThreeWays(nums,gt+1,right);
        }

    }

    // nums[left...lt-1] 都是 小于 pivot 的
    // nums[gt+1...right] 都是 大于 pivot 的
    private static int[] quickThreePartition(int[] nums, int left, int right) {
        int pivot = left;
        // 三个指针，类似于三色旗，这里是三色旗的进阶版，因为多了一个 pivot
        int lt = left + 1;
        int cur = left + 1;
        int gt = right;
        while(cur <= gt){
            if(nums[cur] > nums[pivot]){
                swap(nums,cur,gt);
                gt--;
            }
            else if(nums[cur] < nums[pivot]){
                swap(nums,lt,cur);
                cur++;
                lt++;
            }
            else cur++;
        }
        swap(nums,pivot,lt-1);
        return new int[]{lt-1,gt};
    }
    private static void swap(int[] nums, int p, int q) {
        int temp = nums[p];
        nums[p] = nums[q];
        nums[q] = temp;
    }

插入排序之直接插入排序

/**
 * 直接插入排序
 */
public class EasyInsertSort {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("输入的数的个数：" );
        int len = scanner.nextInt();
        int[] nums = new int[len];

        for(int i = 0;i < len;i++){
            nums[i] = scanner.nextInt();
        }
        EasyInsert(nums);
        System.out.println(Arrays.toString(nums));

    }
    // 直接插入排序， n-1 轮
    private static void EasyInsert(int[] nums) {
        for(int i = 1;i < nums.length;i++){
            int temp = nums[i];
            int j = i;
            while(j > 0 && nums[j-1] > temp){
                nums[j] = nums[j-1];
                j--;
            }
            nums[j] = temp;
        }
    }
}

插入排序之希尔排序

/**
* 其实就是将直接插入排序的间隔1变为更大，也就是其实就多了一个循环，就是多次缩小间隔的循环，其他跟直接插入是一样的
*
* @param sortArray
* @return
*/
public static int[] ShellSort2(int[] sortArray) {
  int[] arr = Arrays.copyOf(sortArray, sortArray.length);
  int size = sortArray.length;
  for (int increment = size / 2; increment > 0; increment /= 2) {
      for (int i = increment; i < size; i++) {
          int temp = arr[i];
          int j = i;
          for (; (j >= increment && arr[j - increment] > temp); j -= increment) {
              //这一步最关键，因为要注意每当插入一个数字，其后面都要往后顺移increment位，不然的话就空不出要插入的位置！！！
              arr[j] = arr[j - increment];
          }
          //如果没有变化，则temp依然等于arr[i],如果变化，则将arr[i]移动过来就行
          arr[j] = temp;
      }
  }
  return arr;
}

选择排序之简单选择排序

/**
 * 简单选择排序
 */
public class SelectSort {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("please input length: ");
        int len = scanner.nextInt();
        int[] nums = new int[len];
        for(int i = 0;i < nums.length;i++){
            nums[i] = scanner.nextInt();
        }
        for(int i = 0;i < nums.length;i++){
            int min = i;
            for(int j = i+1;j < nums.length;j++){
                if(nums[min] > nums[j]) min = j;
            }
            if(min != i) swap(nums,i,min);
        }
        System.out.println(Arrays.toString(nums));
    }

    private static void swap(int[] nums, int i, int min) {
        int temp = nums[i];
        nums[i] = nums[min];
        nums[min] = temp;
    }
}

选择排序之堆排序

/**
 * 堆排序
 */
public class HeapSort {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("要输入的数字的个数：");

        int len = scanner.nextInt();
        int[] nums = new int[len];
        for(int i = 0;i < len;i++){
            nums[i] = scanner.nextInt();
        }
        heapSort(nums,len-1);
        System.out.println(Arrays.toString(nums));
    }

    public static void heapSort(int[] sortArray, int max_index) {
         BuildHeap(sortArray,max_index);
         for(int i = max_index;i > 0;i--){
             swap(sortArray,i,0);
             AdjustDown(sortArray,0,i-1);
         }
    }

    private static void BuildHeap(int[] sortArray, int max_index) {
        double max = max_index;
        for(int i = (int) (Math.round(max/2) - 1); i >= 0; i--){
            AdjustDown(sortArray,i,max_index);
        }
    }

    private static void AdjustDown(int[] sortArray, int i, int max_index) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;
        if(left <= max_index && sortArray[left] > sortArray[largest]){
            largest = left;
        }
        if(right <= max_index && sortArray[right] > sortArray[largest]){
            largest = right;
        }
        if(largest != i){
            swap(sortArray,largest,i);
            AdjustDown(sortArray,largest,max_index);
        }
    }

    private static void swap(int[] sortArray, int largest, int i) {
        int temp = sortArray[largest];
        sortArray[largest] = sortArray[i];
        sortArray[i] = temp;
    }
}

二路归并排序

/**
 * 归并排序
 */
public class mergeSort {
    public static void main(String[] args) {
        int[] nums = new int[]{3,6,7,1,2,3,1,5,7,9,4,2,1,4,5,6};
        mergeSort(nums,0,nums.length-1);
        System.out.println(Arrays.toString(nums));

    }
    public static void mergeSort(int[] nums,int left,int right){
        int mid = left + (right - left)/2;
        if(left < right){
            mergeSort(nums,left,mid);
            mergeSort(nums,mid+1,right);
            mergeTwo(nums,left,mid,right);
        }

    }

    private static void mergeTwo(int[] nums, int left, int mid, int right) {
        // 用一个数组来存储合并后的数组，然后复制给原数组
        int[] temp = new int[right-left+1];
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= right){
            if(nums[i] < nums[j]){
                temp[k++] = nums[i++];
            }
            else {
                temp[k++] = nums[j++];
            }
        }
        while (i <= mid){
            temp[k++] = nums[i++];
        }
        while (j <= right){
            temp[k++] = nums[j++];
        }
        for(int t = 0;t < temp.length;t++){
            nums[left+t] = temp[t];
        }
    }
}

计数排序

/**
 * 计数排序
 */
public class courtSort {
    public static void main(String[] args) {
        int[] nums = new int[]{2,4,1,2,4,1,4,3,2,1,-2,3,1,2,-2,3,4,5,1};
        court(nums);
        System.out.println(Arrays.toString(nums));
    }
    public static void court(int[] nums){
        if(nums.length == 0) return;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i = 0;i < nums.length;i++){
            max = Math.max(max,nums[i]);
            min = Math.min(min,nums[i]);
        }
        int[] temp = new int[max-min+1];
        for(int i = 0;i < nums.length;i++){
            temp[nums[i] - min]++;
        }
        int t = 0;
        for(int i = 0;i < temp.length;i++){
            while (temp[i] != 0){
                nums[t++] = i + min;
                temp[i]--;
            }
        }
    }
}

桶排序

public class BucketSort {
    public static void main(String[] args) {
        int[] array = new int[]{200,123,978,2123,3092,3412,300,321,302,9991,2329,7618,9283};
        radixSort(array);

    }
    public static void radixSort(int[] array) {
        if (array == null || array.length < 2)
            return;
        // 1.先算出最大数的位数；
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            max = Math.max(max, array[i]);
        }
        int maxDigit = 0;
        while (max != 0) {
            max /= 10;
            maxDigit++;
        }
        int mod = 10, div = 1;
        //桶可以用二维数组实现，也可以用ArrayList实现，推荐列表，因为是动态的
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < 10; i++) {
            bucketList.add(new ArrayList<Integer>());
        }
        for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
            for (int j = 0; j < array.length; j++) {
                int num = (array[j] % mod) / div;
                bucketList.get(num).add(array[j]);
            }
            int index = 0;
            for (int j = 0; j < bucketList.size(); j++) {
                for (int k = 0; k < bucketList.get(j).size(); k++) {
                    array[index++] = bucketList.get(j).get(k);
                }
                bucketList.get(j).clear();
            }
        }
        System.out.println(Arrays.toString(array));
    }
}

基数排序

/** 基数排序
  * 可以采用桶的思想，也可以采用队列的思想
  *
  * @param array
  */
 public static void radixSort(int[] array) {
     if (array == null || array.length < 2)
         return;
     // 1.先算出最大数的位数；
     int max = array[0];
     for (int i = 1; i < array.length; i++) {
         max = Math.max(max, array[i]);
     }
     int maxDigit = 0;
     while (max != 0) {
         max /= 10;
         maxDigit++;
     }
     int mod = 10, div = 1;
     //桶可以用二维数组实现，也可以用ArrayList实现，推荐列表，因为是动态的
     ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
     for (int i = 0; i < 10; i++) {
         bucketList.add(new ArrayList<Integer>());
     }
     for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
         for (int j = 0; j < array.length; j++) {
             int num = (array[j] % mod) / div;
             bucketList.get(num).add(array[j]);
         }
         int index = 0;
         for (int j = 0; j < bucketList.size(); j++) {
             for (int k = 0; k < bucketList.get(j).size(); k++) {
                 array[index++] = bucketList.get(j).get(k);
             }
             bucketList.get(j).clear();
         }
     }
     System.out.println(Arrays.toString(array));
 }

二叉树遍历

这里只提供二叉树遍历模板，具体有关二叉树的内容可以移步我的另外一篇文章：二叉树专题总结

前序

递归

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        preorderHelper(root, result);
        return result;
    }

    private void preorderHelper(TreeNode root, List<Integer> result) {
        if (root == null) return;
        result.add(root.val); // 访问根节点
        preorderHelper(root.left, result); // 递归遍历左子树
        preorderHelper(root.right, result); //递归遍历右子树
    }
}

非递归

// 1.1 非递归先序
private static void preOrder(TreeNode root) {
    ArrayList<Integer> arrayList = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            arrayList.add(cur.val);
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        cur = cur.right;
    }
    System.out.println(arrayList);
}


// 1.2 非递归先序2
private static void preOrder2(TreeNode root) {
    ArrayList<Integer> arrayList = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    stack.push(cur);
    while (!stack.isEmpty()) {
        cur = stack.pop();
        arrayList.add(cur.val);
        if (cur.right != null) stack.push(cur.right);
        if (cur.left != null) stack.push(cur.left);
    }
    System.out.println(arrayList);
}

中序

递归

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        preorderHelper(root, result);
        return result;
    }

    private void preorderHelper(TreeNode root, List<Integer> result) {
        if (root == null) return;
        preorderHelper(root.left, result); // 递归遍历左子树
        result.add(root.val); // 访问根节点
        preorderHelper(root.right, result); //递归遍历右子树
    }
}

非递归

// 2. 中序非递归
private static void InOrder(TreeNode root) {
    ArrayList<Integer> arrayList = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        arrayList.add(cur.val);
        cur = cur.right;
    }
    System.out.println(arrayList);
}

后序

递归

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        preorderHelper(root, result);
        return result;
    }

    private void preorderHelper(TreeNode root, List<Integer> result) {
        if (root == null) return;
        preorderHelper(root.left, result); // 递归遍历左子树
        preorderHelper(root.right, result); //递归遍历右子树
        result.add(root.val); // 访问根节点
    }
}

非递归

//3. 后序非递归 左右根 反过来讲就是 根右左
private static void postOrder(TreeNode root) {
    ArrayList<Integer> arrayList = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            arrayList.add(cur.val);
            stack.push(cur);
            cur = cur.right;
        }
        cur = stack.pop();
        cur = cur.left;
    }
    Collections.reverse(arrayList);
    System.out.println(arrayList);
}

层序

递归

public List<List<Integer>> levelOrder(Node root) {
    if (root == null) return res;
    List<List<Integer>> res = new ArrayList<>();
    helper(root, 0, res);
    return res;
}
private void helper(Node root, int depth, List<List<Integer>> res) {
    if (root == null) return;
    //判断是否是新的一层
    if (depth + 1 > res.size()) {
        res.add(new ArrayList<>());
    }
    res.get(depth).add(root.val);

    //处理子节点
    for (Node node : root.children) {
        if (node != null) {
            helper(node, depth + 1, res);
        }
    }
}

非递归

//4.1 层序遍历
private static void levelOrder(TreeNode root) {
    ArrayList<Integer> arrayList = new ArrayList<>();
    Queue<TreeNode> queue = new ArrayDeque<>();
    TreeNode cur = root;
    queue.add(cur);
    while (!queue.isEmpty()) {
        cur = queue.poll();
        arrayList.add(cur.val);
        if (cur.left != null) queue.add(cur.left);
        if (cur.right != null) queue.add(cur.right);
    }
    System.out.println(arrayList);
}



//4.2 层序遍历 2
private static void levelOrder2(TreeNode root) {
    ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
    Queue<TreeNode> queue = new ArrayDeque<>();
    TreeNode cur = root;
    queue.add(cur);
    int count;
    while (!queue.isEmpty()){
        ArrayList<Integer> arrayList = new ArrayList<>();
        count = queue.size();
        while (count > 0){
            cur = queue.poll();
            count--;
            arrayList.add(cur.val);
            if(cur.left != null) queue.add(cur.left);
            if(cur.right != null) queue.add(cur.right);
        }
        arrayLists.add(arrayList);
    }
    System.out.println(arrayLists);
}

二分

面试的时候经常碰到二分，比如求根号n，求最左侧target的下标，求翻转后的有序数组对应的最左侧target下标等等。

模板

左闭右开

public class binarySearch {
    int binarySearch(int nums[],int target){
        int left = 0;
        int right = nums.length; // 查找范围为 [a,b)
        while(left < right){ // left == right 时退出，此时[a,a)，所以此时都遍历到了
            //防止计算mid时溢出
            int mid = left + (right - left) / 2;
            if(nums[mid] == target)
                return mid;
            else if(nums[mid] < target)
                left = mid + 1;
            else if(nums[mid] > target)
                right = mid;
        }
        return -1;
    }

    /**
     * 返回的是比target小的数量，同时也是最左target的下标
     * @param nums
     * @param target
     * @return
     */
    int binarySearchLeft(int nums[],int target){
        int left = 0;
        int right = nums.length;
        while(left < right){
            //防止计算mid时溢出
            int mid = left + (right - left) / 2;
            if(nums[mid] == target)
                right = mid;
            else if(nums[mid] < target)
                left = mid + 1;
            else if(nums[mid] > target)
                right = mid;
        }
        //要时刻注意处理边界，如果整个数组都没有这个target，则left会到nums.length
        //left的取值是[0,nums.length]
        // target 比所有数都大
        if (left == nums.length) return -1;
        // 类似之前算法的处理方式
        return nums[left] == target ? left : -1;
    }

    /**
     * 返回的是最右target的下标
     * @param nums
     * @param target
     * @return
     */
    int binarySearchRight(int nums[],int target){
        int left = 0;
        int right = nums.length;
        while(left < right){
            //防止计算mid时溢出
            int mid = left + (right - left) / 2;
            if(nums[mid] == target)
                left = mid + 1;
            else if(nums[mid] < target)
                left = mid + 1;
            else if(nums[mid] > target)
                right = mid;
        }
        //要时刻注意处理边界，如果整个数组都没有这个target，则left会到nums.length
        // target 比所有数都大
        // return left - 1;
        if (left == 0) return -1;
        // 类似之前算法的处理方式
        return nums[left-1] == target ? (left-1) : -1;
    }
}

左闭右闭

package 二分查找;

import java.util.Arrays;

public class binarySearch2 {
    public static void main(String[] args) {
        binarySearch2 binarySearch2 = new binarySearch2();
        int[] nums = new int[]{1,2,2,2,2,2,3};
        int target = 2;
//        int res = binarySearch2.binarySearch(nums,target);
//        int res = binarySearch2.binarySearchLeft(nums,target);
        int res = binarySearch2.binarySearchRight(nums,target);
        System.out.println(res);


    }

    public int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] > target) right = mid - 1;
            else if (nums[mid] < target) left = mid + 1;
        }
        return -1;
    }


    public int binarySearchLeft(int[] nums,int target){
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left)/2;
            if(nums[mid] == target) right = mid - 1;
            else if(nums[mid] > target) right = mid -1;
            else if(nums[mid] < target) left = mid + 1;
        }
        if(left >= nums.length || nums[left] != target){
            return -1;
        }
        return left;
    }

    public int binarySearchRight(int[] nums,int target){
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 别返回，锁定右侧边界
                left = mid + 1;
            }
        }
        // 最后要检查 right 越界的情况，这里 left = right + 1
        if (right < 0 || nums[right] != target)
            return -1;
        return right;
    }
}

相关题目

根号n

package 练手算法;


import java.text.DecimalFormat;

class Main {

    public static double sqrt(double num) {
        if (num < 0) {
            return -1;
        }

        double low = 0;
        double high = num / 2;
        double precision = 0.000001;
        //格式化，保证输出位数
        DecimalFormat df = new DecimalFormat("#.00");

        double res = high;
        while (Math.abs(num - (res * res)) > precision) {
            if (high * high > num) {
                double n = high - (high - low) / 2;
                if (n * n > num) {
                    high = n;
                } else if (n * n < num) {
                    low = n;
                } else {
                    return Double.valueOf(df.format(n));
                }
                res = n;

            } else if (high * high < num) {
                double m = high + (high - low) / 2;
                if (m * m > num) {
                    low = high;
                    high = m;
                } else if (m * m < num) {
                    low = high;
                    high = m;
                } else {
                    return Double.valueOf(df.format(m));
                }
                res = m;
            } else {
                return Double.valueOf(df.format(high));
            }
        }

        return Double.valueOf(df.format(res));
    }

    public static void main(String[] args) {
        System.out.println(sqrt(16));
    }
}

public class SqrtN {
    public static void main(String[] args) {

    }

}

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

题目

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

代码

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums.length == 0) return new int[]{-1,-1};
        return new int[]{searchLeft(nums,target),searchRight(nums,target)};
    }
    
    public int searchLeft(int[] nums,int target){
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            // 防止溢出
            int mid = left + (right - left)/2;
            if(nums[mid] >= target) right = mid - 1;
            else left = mid + 1;
        }
        // 上面的while循环后，最后一次循环 left == mid, right = left - 1 = mid - 1
        // 若有符合要求的target，则会有两种情况：
        // 1. left 和 right 在 target 值的最左索引处的前一位相遇，此时 left 会向右一位，到达最左 target 处,而 right 会停在原地，弹出 while
        // 2. left 和 right 在 target 值的最左索引处相遇，此时 left 不动，到达最左 target 处,而 right 会向左一位，弹出 while
        // 注意：此时的 left 都是处在 target 最左索引处
        // 如果没有符合要求的target，则有三种情况：
        // 1.所有值均小于target，此时，left会在 nums[nums.length-1]处与right相遇，然后left 加 1，跳出循环，此时left == nums.length
        // 2.所有值均大于target，此时right会不断向左，直至 left = right = 0 相遇，此时 right 减 1，跳出循环，此时 left == 0
        // 3.target位于值的中间，但是没有值取到，此时跟有target情况是类似的，最终 left 会停留在比 target 大的第一个数上 
        // 总结上面 5 种情况，left 为 nums.length 时，另其为 nums.length - 1,此时直接判断 nums[left] 即可，若为target则直接返回 left
        // 否则返回 -1
        int pos = (left == nums.length) ? nums.length - 1 : left;
        if(nums[pos] != target) return -1;
        return left;
    }
    
    public int searchRight(int[] nums,int target){
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            // 防止溢出
            int mid = left + (right - left)/2;
            if(nums[mid] <= target) left = mid + 1;
            else right = mid - 1;
        }
        // 同上分析
        int pos = (right == -1)? 0 : right;
        if(nums[pos] != target) return -1;
        return right;
    }
}

33. 搜索旋转排序数组

题目

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

代码

class Solution {
    public int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        while(start <= end){
            int mid = start + (end - start)/2;
            if(nums[mid] == target) return mid;
            if (nums[start] == nums[mid]) {
                start++;
                continue;
            }
            //最容易错的点，就是列表只有两个数字时，mid和start是同一个数，此时必须是前半部分有序
            // num[mid] == nums[start] 只会在列表只有两个数时才相等，所以才可以上面那样处理
            // 正常其实是不应该那样处理，而应该是当num[mid] == nums[start]，直接start++，然后进行下一次循环
            if(nums[mid] > nums[start]){
                // 说明前半部分有序
                if(nums[start] <= target && target < nums[mid]){
                    end = mid - 1;
                }
                else {
                    start = mid + 1;
                }
            }
            else {
                // 说明后半部分有序
                if(nums[mid] < target && target <= nums[end]){
                    start = mid + 1;
                }
                else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }
}

81. 搜索旋转排序数组 II

在上面的基础上，去除不可重复，这里的数组中的元素包含了可重复的元素，同时加大难度，要求找出第左侧的target的下标「这个我不会 」。

class Solution {
    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int start = 0;
        int end = nums.length - 1;
        int mid;
        while (start <= end) {
            mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[start] == nums[mid]) {
                start++;
                continue;
            }
            //前半部分有序
            if (nums[start] <= nums[mid]) {
                //target在前半部分
                if (nums[mid] > target && nums[start] <= target) {
                    end = mid - 1;
                } else {  //否则，去后半部分找
                    start = mid + 1;
                }
            } else {
                //后半部分有序
                //target在后半部分
                if (nums[mid] < target && nums[end] >= target) {
                    start = mid + 1;
                } else {  //否则，去后半部分找
                    end = mid - 1;

                }
            }
        }
        //一直没找到，返回false
        return false;

    }
}

287. 寻找重复数

题目

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

代码

class Solution {
    public int findDuplicate(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left)/2;
            int count = 0;
            int mid_count = 0;
            for(int i = 0;i < nums.length;i++){
                if(nums[i] <= mid) count++;
                if(nums[i] == mid) mid_count++;
            }
            // 如果 [left,mid] 没有出现重复数字，count <= mid
            // 否则说明在这个区间出现了重复的
            // 这里跟常见的 二分有一点点不同，这里 right = mid，不是 right = mid - 1
            // 因为我在上面计算 count 的时候 是有计算 mid 的
            if(mid_count > 1) return mid;
            if(count > mid) right = mid - 1;
            else left = mid + 1;
        }
        return -1;
    }
}