Weitanai

# 二分查找

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

# 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

class Solution {
    public int search(int[] nums, int target) {
        int lo =0, hi = nums.length-1;
        
        while(hi >= lo){
            int mid = lo+(hi-lo)/2;
            if(nums[mid] == target){
                return mid;
            }
            else if(nums[mid] > target){
                hi = mid-1;
            }
            else if(nums[mid] < target){
                lo = mid+1;
            }
        }
        return -1;
    }
}

# 2寻找峰值

峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞。

示例 1

输入: nums = [1,2,3,1]

输出: 2

解释: 3 是峰值元素，你的函数应该返回其索引 2。

class Solution {
    public int findPeakElement(int[] nums) {
        int lo = 0, hi = nums.length-1;
        while(hi>=lo){
            int mid = (hi+lo)/2;
            if(nums[mid]> nums[mid+1]){
                hi = mid-1;
            }else{
                lo = mid+1;
            }
        }
        return lo;
    }
}

2
    
    class Solution {
    public int findPeakElement(int[] nums) {
        int lo = 0, hi = nums.length-1;
        for(int i =0; i<hi; i++){
            if(nums[i]>nums[i+1]{
            return i
                }
        }
    }
}

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

# 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;
    }
// 中序遍历二叉树得到有序数组， 递归的思想

← 双指针 →