• 二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法，前提是数据结构必须先排好序，可以在数据规模的对数时间复杂度内完成查找。但是，二分查找要求线性表具有有随机访问的特点（例如数组），也要求线性表能够根据中间元素的特点推测它两侧元素的性质，以达到缩减问题规模的效果

关键点

  • while 循环时 hi与lo有没有等号， 决定以后的 mid 赋值给hi 与 lo的程度。

0 具体实践

  • 寻找特定值是分成 三段判等，
  • 寻找峰值时，Mid 与左右两边对比

1 数组

  • 二分搜索， 寻找比目标字母大的最小字母， 峰值查找，搜索二维矩阵

2 树

  • 二叉搜索树第k小的元素

1 数组实例

1 二分搜索


给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.         int lo =0, hi = nums.length-1;
  5.         while(hi >= lo){
  6.             int mid = lo+(hi-lo)/2;
  7.             if(nums[mid] == target){
  8.                 return mid;
  9.             }
  10.             else if(nums[mid] > target){
  11.                 hi = mid-1;
  12.             }
  13.             else if(nums[mid] < target){
  14.                 lo = mid+1;
  15.             }
  16.         }
  17.         return -1;
  18.     }
  19. }

2寻找峰值

峰值元素是指其值大于左右相邻值的元素。
给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。
数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞。
示例 1
输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素，你的函数应该返回其索引 2。

  1. class Solution {
  2.     public int findPeakElement(int[] nums) {
  3.         int lo = 0, hi = nums.length-1;
  4.         while(hi>=lo){
  5.             int mid = (hi+lo)/2;
  6.             if(nums[mid]> nums[mid+1]){
  7.                 hi = mid-1;
  8.             }else{
  9.                 lo = mid+1;
  10.             }
  11.         }
  12.         return lo;
  13.     }
  14. }
  16. 2
  18.     class Solution {
  19.     public int findPeakElement(int[] nums) {
  20.         int lo = 0, hi = nums.length-1;
  21.         for(int i =0; i<hi; i++){
  22.             if(nums[i]>nums[i+1]{
  23.             return i
  24.                 }
  25.         }
  26.     }
  27. }

3二维矩阵搜索

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
示例 1:
输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
输出: true

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {

        int m = matrix.length;
        if(m == 0)  return false;
        int n  =matrix[0].length;
        int lo = 0, hi = m*n-1;

        while(hi >= lo){
            int mid = lo+(hi-lo)/2;
            int r = mid/n;
            int c = mid%n;
            int part = matrix[r][c];
            if( part== target){
                return true;
            }
            else if(part < target){
                lo = mid+1;
            }else{
                hi = mid-1;
            }
        }
        return false;

    }
}
// 二维数组展开成一位， 二维数组的中点转换，
            // int mid = lo+(hi-lo)/2;
            // int r = mid/n;
            // int c = mid%n;

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

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        // HashMap<Integer, Integer> map = new HashMap<>();
        int len = nums.length;
        if(nums == null || len<3)   return  list;
        Arrays.sort(nums);
        for(int i = 0; i<len; i++){
            if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
            if(i > 0 && nums[i] == nums[i-1]) continue; // 去重

            int l = i+1;
            int r = len-1;
            while(l<r){
                int sum = nums[i]+nums[l]+nums[r];
                if(sum == 0){
                    list.add(Arrays.asList(nums[i],nums[l],nums[r]));
                    while (l<r && nums[l] == nums[l+1]) l++; // 去重
                    while (l<r && nums[r] == nums[r-1]) r--; // 去重
                    l++;
                    r--;
                }
                else if (sum < 0) l++;
                else if (sum > 0) r--;
            }
        }
        return list;
    }
}

5 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

class Solution {
    public int threeSumClosest(int[] nums, int target) {

        Arrays.sort(nums);
        int lo = 0, hi = nums.length;
        if(nums == null || hi < 3) return -1;
        int ans = nums[0]+nums[1]+nums[2];

        for(int i = 0; i<hi; i++){
            int start = i+1, end = hi-1;
            while(start < end){       
                int sum = nums[i] + nums[start] +nums[end];
                if(Math.abs(sum -target)< Math.abs(ans - target))
                ans = sum;
                if(sum > target){
                    end--;
                }else if(sum < target){
                    start++;
                }else{
                    return sum;
                }
            }
        }
        return ans;

    }
}

5

744. 寻找比目标字母大的最小字母

难度简单68
给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。
在比较时，字母是依序循环出现的。举个例子：

  • 如果目标字母 target = 'z' 并且字符列表为 letters = ['a', 'b']，则答案返回 'a'


    示例：
    输入:
    letters = [“c”, “f”, “j”]
    target = “a”
    输出: “c”

输入:
letters = [“c”, “f”, “j”]
target = “j”
输出: “c”

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {

        int lo = 0; 
        int  hi = letters.length-1;
        if(letters[0]>target || letters[hi] <= target){
            return letters[0];
        }
        while(hi>= lo){
            int mid = lo+(hi-lo)/2;
            if(letters[mid] <= target){
                lo = mid+1;
            }else{
                if(letters[mid-1] <= target){
                    return letters[mid];
                }else{
                    hi = mid-1;
                }
            }
        }
        return ' ';
    }
}

2 树实例

1二叉搜索树中第k小的元素

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 1

class Solution {
    private int i = 0;
    private int val = 0;
    public void dfs(TreeNode root, int k) {
        if (root == null) {
            return;
        }
        dfs(root.left, k);
        if (k == ++i) {
            val = root.val;
        }
        dfs(root.right, k);
    }
    public int kthSmallest(TreeNode root, int k) {
        dfs(root, k);
        return val;
    }
// 中序遍历二叉树得到有序数组， 递归的思想