算法六 二分查找与二叉排序树（Java实现）
二分查找
二分查找又称折半查找。首先，假设表中元素是按升序排列，将表中间位置的关键字与查找关键字比较：
1.如果两者相等，则查找成功；
2.否则利用中间位置将表分成前、后两个子表：1)如果中间位置的关键字大于查找关键字，则进一步查找前一子表；2)否则进一步查找后一子表。
重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
二叉查找(排序)树
二叉查找树(Binary Search Tree),它是-颗具有下列性质的二叉树:
1.若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值。
2.若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值。
3.左、右子树也分别为二叉排序树。
4.等于的情况只能出现在左子树或右子树中的某一侧。
由于二叉查找树的中序遍历是从小到大的，故又名二叉排序树(Binary Sort Tree)。
二叉查找树插入节点
将某节点(insert node), 插入至以node为根二叉查找树中:
如果insert _node节点值小于当前node节点值:如果node有左子树，则递归的将该节点插入至左子树为根二叉排序树中；否则，将node->left赋值为该节点地址。
否则(大于等于情况): 如果node有右子树，则递归的将该节点插入至右子树为根二叉排序树中；否则，将node->right赋值为该节点地址。
二叉查找树查找数值
查找数值value是否在二叉查找树中出现:
如果value等于当前查看node的节点值:返回真。
如果value节点值小于当前node节点值:如果当前节点有左子树，继续在左子树中查找该值;否则，返回假。
否则(value节点值大于当前node节点值):如果当前节点有右子树，继续在右子树中查找该值;否则，返回假。
1、LeetCode35搜索插入位置
class Solution { 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; } else if(target < nums[mid]){ if(mid == 0||target > nums[mid-1]){ index = mid; } end = mid-1;//如果target小于中点，更新区间右端点 } else if(target > nums[mid]){ if(mid == nums.length-1||target < nums[mid+1]){ index = mid+1; } begin = mid+1;//如果target大于中点，更新区间左端点 } } return index; } } 复制代码2、LeetCode34在排序数组中查找元素的第一个和最后一个位置
思路：查找区间左端点时，增加如下限制条件：当target == nums[mid]时，若此时mid == 0或nums[mid-1] < target，则说明mid即为区间左端点，返回；否则设置区间右端点为mid-1。查找区间右端点时，增加如下限制条件：当target == nums[mid]时，若此时mid == nums.size()- 1或nums[mid + 1]>target，则说明mid即为区间右端点；否则设置区间左端点为mid + 1。
class Solution { public int[] searchRange(int[] nums, int target) { int leftIdx = left_bound(nums, target); int rightIdx = right_bound(nums, target); if (leftIdx <= rightIdx && rightIdx < nums.length) { return new int[]{leftIdx, rightIdx}; } return new int[]{-1, -1}; } public int left_bound(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = (left + right) / 2; if (target == nums[mid]){ if (mid == 0||nums[mid-1] < target){ return mid; } right = mid - 1; } else if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] < target){ left = mid + 1; } } return -1; } public int right_bound(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = (left + right) / 2; if (target == nums[mid]){ if (mid == nums.length - 1||nums[mid+1] > target){ return mid; } left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] < target){ left = mid + 1; } } return -1; } } 复制代码3、LeetCode33搜索旋转排序数组
思路：nums[begin]>nums[end]
class Solution { public int search(int[] nums, int target) { int begin = 0,end = nums.length-1; while(begin <= end){ int mid = (begin+end)/2; if(target == nums[mid]){ return mid; } else if(target < nums[mid]){ if(nums[begin] < nums[mid]){ if(target >= nums[begin]){ end = mid-1; }else{ begin = mid+1; } }else if(nums[begin] > nums[mid]){ end = mid-1; }else if(nums[begin] == nums[mid]){ begin = mid+1; } } else if(target > nums[mid]){ if(nums[begin] < nums[mid]){ begin = mid+1; }else if(nums[begin] > nums[mid]){ if(target >= nums[begin]){ end = mid-1; }else{ begin = mid+1; } }else if(nums[begin] == nums[mid]){ begin = mid+1; } } } return -1; } } 复制代码leetcode官方题解
class Solution { public int search(int[] nums, int target) { int n = nums.length; if (n == 0) { return -1; } if (n == 1) { return nums[0] == target ? 0 : -1; } int l = 0, r = n - 1; while (l <= r) { int mid = (l + r) / 2; if (nums[mid] == target) { return mid; } if (nums[0] <= nums[mid]) { if (nums[0] <= target && target < nums[mid]) { r = mid - 1; } else { l = mid + 1; } } else { if (nums[mid] < target && target <= nums[n - 1]) { l = mid + 1; } else { r = mid - 1; } } } return -1; } } 复制代码4、LeetCode449序列化和反序列化二叉搜索树
思路：二叉查找树编码为字符串：将二叉查找树前序遍历，遍历时将整型的数据转为字符串，并将这些字符串数据进行连接，连接时使用特殊符号分隔。
将字符串解码为二叉查找树：将字符串按照编码时的分隔符”#”，将各个数字逐个拆分出来，将第一个数字构建为二叉查找树的根节点，后面各个数字构建出的节点按解析时的顺序插入根节点中,返回根节点，即完成了解码工作。
LeetCode评论代码
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Codec { // Encodes a tree to a single string. public String serialize(TreeNode root) { if (root == null) { return ""; } StringBuilder sb = new StringBuilder(); BST_preorder(root, sb);//将root指向的树转为字符串sb return sb.substring(0, sb.length() -1); } // 前序遍历二叉排序树，将root.val转换为字符串存储至sb private void BST_preorder(TreeNode root, StringBuilder sb) { if (root == null) { return; } sb.append(root.val).append("#"); BST_preorder(root.left, sb); BST_preorder(root.right, sb); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { if (data.isEmpty()) { return null; } String[] split = data.split("#"); return buildTreeNode(split, 0, split.length -1); } private static TreeNode buildTreeNode(String[] split, int left, int right) { if (left > right) { return null; } TreeNode root = new TreeNode(Integer.parseInt(split[left])); int index = right + 1; for (int i = left + 1; i <= right; i++) { if (Integer.parseInt(split[i]) > root.val) { index = i; break; } } root.left = buildTreeNode(split, left + 1, index -1); root.right = buildTreeNode(split, index, right); return root; } } // Your Codec object will be instantiated and called as such: // Codec ser = new Codec(); // Codec deser = new Codec(); // String tree = ser.serialize(root); // TreeNode ans = deser.deserialize(tree); // return ans;
作者：zust_Isabella
链接：https://juejin.cn/post/7002129809568595998