二分查找和二叉排序树

大大源码 • 2023年3月19日 pm11:09 • 其他

二分查找和二叉排序树

预备知识

1 二分查找算法

前提：要有顺序

逻辑（默认升序）：

将中间位置的关键字与查询关键字比较：

如果两者相等，则查找成功。
否则利用中间位置将表分成前、后两个子表：
1. 如果中间位置的的关键字大于查找关键字，则进一步查找前一子表
2. 否则进一步查找后一字表

重复以上过程，直到找到满足条件的记录，则查询成功，或这直到子表不存在为止，此时查找不成功。

//递归
public static boolean binary_search(int[] val,int begin,int end,int target){
        if(begin>end){
            return false;
        }
        int mid = (begin+end)/2;
        if(target == val[mid]) return true;
        else if(target < val[mid]){
            return binary_search(val,begin,mid-1,target);
        }else{
            return binary_search(val,mid+1,end,target);
        }
    }
	//非递归
    public static boolean binary_search_no_recursive(int[] val,int target){

        int begin = 0;
        int end = val.length-1;

        while(begin <= end){
            int mid = (begin+end)/2;
            if (target==val[mid]) {
                return true;
            }else if (target < val[mid]){
                end = mid-1;
            }else{
                begin = mid+1;
            }
        }
        return false;

    }

这里说明下什么时候使用递归什么时候循环：本人觉得如果整个思路是用分治思路的就可以用循环，如果类似回溯思路的就用递归。

2、二叉查找（排序）树

二叉查找树，它是一颗具有下列性质的二叉树：

若左子树不为空，则左子树上所有结点的值均小于或等于它的根节点的值
右子树是大于等于
左右子树分别是二叉排序树
等于的情况只能出现在左子树或右子树的某一侧

class TreeNode{
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(int x){this.val = x; this.left = null; this.right=null；}
}

由于二叉查找树的中序遍历是从小到大的，所有又叫做二叉排序树；

二叉排序树的插入算法

public static void insert(TreeNode root,TreeNode insert_node){
		//判断插入左子树还是右子树
        if(insert_node.val < root.val){
            //如果该节点的左子树为null插入
            if(root.left == null){
                root.left = insert_node;
            }
            //不为null 递归
            else{
                insert(root.left,insert_node);
            }
        }else{
            if(root.right == null){
                root.right = insert_node;
            }else{
                insert(root.right,insert_node);
            }
        }
    }

二叉排序树查找算法

public static boolean search(TreeNode root, int value){
    if(root.val == value) return true;
    if(root.val > value){
        if(root.left != null){
            return search(root.left,value);
        }else {
            return false;
        }

    }else{
        if(root.right != null){
           return search(root.right,value);
        }
        else {
            return false;
        }
    }
}

实战1：二分查找

LeetCode 35 搜索插入位置

思路：

二分查找，判断条件改为搜索到位置为止，index
临界点考虑清楚，第一个元素和最后一个元素

 public int searchInsert(int[] nums, int target) {
        int index = -1;
        int begin = 0;
        int end = nums.length -1;
        while(index ==-1){
            int mid = (begin + end)/2;
            if(target == nums[mid]){
                index = mid;
                break;
            }else if(target < nums[mid]){
                //这里需要考虑临界点，如果是在小于mid得区间，就要先判断是不是已经是第一个元素了
                if(mid == 0 ||target > nums[mid -1]){
                    index = mid;
                }
                end = mid -1;
            }else{
                if(mid == nums.length-1||target < nums[mid+1]){
                    index = mid+1;
                }
                begin = mid+1;
            }
        }
        return index;
    }

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

思路：

二分查找，第一次查最左边的边界。第二次查最右边的边界。
改造二分查找，如果找到一个target,要判断它左边或者右边是否存在相同的元素。如果存在则改变二分查找的begin(右边界)，或者end（左边界）。

public int[] searchRange(int[] nums, int target) {
        int[] res = new int[2];
        res[0] = searchRangeLeft(nums,target);
        res[1] = searchRangeRight(nums,target);
        return res;
    }
    public int searchRangeLeft(int[] nums,int target){
        int begin = 0;
        int end = nums.length -1;
        int index = -1;
        while(begin <= end){
            int mid = (begin+end)/2;
            if(target == nums[mid]){
                //如果是最左边界，或者是下一个左边元素不是target了，就得到了我们最左边界
                if(mid == 0 || nums[mid-1]!= target){
                    index = mid;
                    break;
                }else{//将我们的end指针指到左边和它相同的元素
                    end = mid -1;
                }
            }else if(target < nums[mid]){
                end = mid -1;
            }else{
                begin = mid+1;
            }
        }
        return index;
    }
    public int searchRangeRight(int[] nums,int target){
        int begin = 0;
        int end = nums.length -1;
        int index = -1;
        while(begin <= end){
            int mid = (begin+end)/2;
            if(target == nums[mid]){
                if(mid == nums.length-1 || nums[mid+1]!= target){
                    index = mid;
                    break;
                }else{
                    begin = mid + 1;
                }
            }else if(target < nums[mid]){
                end = mid -1;
            }else{
                begin = mid+1;
            }
        }
        return index;
    }

LeetCode 33 搜索旋转排序数组

思路：

首先能想到的是根据val[mid]为切分点不管怎么样旋转数组肯定存在一部分是有序的；
如果target在那一部分有序的部分，直接调整begin和end指针在有序部分的集合里面二分搜索就可以找到target；
如果target不在那一部分有序的数组，那么我们就调整指针在无序的数组里面按照1的思路找。

代码：

public int search(int[] nums, int target) {
    	//处理特殊情况
       if(nums== null || nums.length==0) return -1;
       if(nums.length == 1) return target==nums[0]?0:-1;
       int begin = 0;
       int end = nums.length -1;
       while(begin <= end){
           int mid = (begin+end)/2;
           if(target == nums[mid]) return mid;
           //判断mid前面的数组是否有序
           if(nums[0] <= nums[mid]){
               //判断target是不是在前面数组的范围
               if(nums[0]<=target&&target < nums[mid]){
                   //在的话，就在这个范围里面二分
                   end = mid-1;
               }
               //如果不在，说明在后面的无序数组里面，去无序数组里继续查找
               else{
                   begin = mid+1;
               }
           }//无序，说明后面的转到前面了，也就是mid 到 最后一个元素肯定有序
           else {
               //判断target是不是在有序的集合里面
               if(target <= nums[nums.length-1]&& target > nums[mid]){
                   begin =  mid+1 ;
               }else{
                   end = mid-1;
               }
           }
       }
       return -1;
    }

实战2：二叉搜索树

LeedCode 449. 序列化和反序列化二叉搜索树

思路：

首先了解序列化的意义，就是把我们的对象转换成string，使它能够在网络或者文件传播和存储。反序列化就是拿到序列化的string之后，可以转换成对应的对象。
将树转换成String的过程，就是遍历树的过程，这里就是要考虑怎么遍历？前中后？重点是遍历之后存储在取得时候能够还原原来得顺序。这里采取得是先序遍历，因为这样就按照根左右得方式，这样存储得顺序就是根-》左-》右，那么我们在进行插入得时候，刚好保持了原来的顺序。

代码：

 public String serialize(TreeNode root) {
        if(root ==null) return "";
        StringBuilder res = new StringBuilder();
     //先序遍历。转换成字符串
        preTree(root,res);
        return res.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data== null || data.length() == 0) return null;
        //获取先序节点数组
        String[] vals = data.split("#");
        //先定义根节点
        TreeNode root = new TreeNode(Integer.valueOf(vals[1]));
        //逐个将节点插入进去
        for(int i =2; i<vals.length; i++){
            insert(root,new TreeNode(Integer.valueOf(vals[i])));
        }
        return root;
    }
//树得先序遍历
    public void preTree(TreeNode root , StringBuilder res){
        if(root == null) return;
        res.append("#"+root.val);
        preTree(root.left,res);
        preTree(root.right,res);
    }
//二叉树排序树得插入算法
    public void insert(TreeNode root ,TreeNode insertNode){
        if(root == null) {
            root = insertNode;
            return;
        }
        if(insertNode.val < root.val){
            if(root.left == null){
                root.left = insertNode;
            }else{
                insert(root.left,insertNode);
            }
        }else{
            if(root.right == null){
                root.right = insertNode;
            }else{
                insert(root.right,insertNode);
            }
        }
    }

LeedCode 315、计算右侧小于当前元素的个数

思路：

其实最先想到的肯定暴力解法。遍历就完事了。这样的时间复杂度就On方了。
如果我们把集合逆序，就变成了求集合中元素，前面有多少比它小的元素。求出之后，在逆序回来就可以了
如果是求集合前面又多少元素的话，就可以转换成二叉排序树的插入过程，因为插入的时候比它小就肯定在左边，这是我们一个判断条件。
这时候，我们的节点需要多一个左子树个数，记录比它小的个数，我们称之为leftCounts。
上面考虑了插入在左子树的情况，如果是插入的节点比根节点大呢？这时候就要更新我们想要的结果，也就是在它插入之前，比它小的个数。这个个数我们记录为smallCount, 它应该等于它的根节点的leftCounts + 1。这样就得到了每一个节点的smllCount，在逆置就可以了。

代码：

class Solution {
    static class BTSNode{
        int val;
        int leftCounts;
        BTSNode left;
        BTSNode right;
        BTSNode( int val){
            this.val = val;
            leftCounts = 0;
            left = null;
            right = null;
        }
    }
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = null;
        Integer[] resArray = new Integer[nums.length];
        Arrays.fill(resArray,0);
        List<BTSNode> nodes = new ArrayList<>();
        for(int i = nums.length -1; i>=0 ; i--){
            nodes.add(new BTSNode(nums[i]));
        }
       for(int i =1; i<nodes.size(); i++){
           insert(nodes.get(0),nodes.get(i),i,resArray);
       }
       res= Arrays.asList(resArray);
       Collections.reverse(res);
        return res;
    }

    public void insert(BTSNode root, BTSNode insertNode, int index , Integer[] res){
        if(insertNode.val <= root.val){
            root.leftCounts++;
            if(root.left == null){
                root.left = insertNode;
            }else{
                insert(root.left,insertNode,index,res);
            }
        }else{
            res[index]+= root.leftCounts +1;
            if(root.right == null){
                root.right = insertNode;
            }else{
                insert(root.right,insertNode,index,res);
            }
        }
    }
}

原文链接：https://blog.csdn.net/qq_36628536/article/details/110234172

THE END

Raw use of parameterized class 处理

< <上一篇

OFDM基本原理（正交性、傅里叶变换、ISI、ICI、循环前缀）

下一篇>>

大大搜源码

搜索内容

二分查找和二叉排序树

二分查找和二叉排序树

预备知识

1 二分查找算法

2、二叉查找（排序）树

实战1：二分查找

LeetCode 35 搜索插入位置

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

LeetCode 33 搜索旋转排序数组

实战2：二叉搜索树

LeedCode 449. 序列化和反序列化二叉搜索树

LeedCode 315、计算右侧小于当前元素的个数

二分查找和二叉排序树

二分查找和二叉排序树

预备知识

1 二分查找算法

2、二叉查找（排序）树

实战1： 二分查找

LeetCode 35 搜索插入位置

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

LeetCode 33 搜索旋转排序数组

实战2： 二叉搜索树

LeedCode 449. 序列化和反序列化二叉搜索树

LeedCode 315、计算右侧小于当前元素的个数

实战1：二分查找

实战2：二叉搜索树