大家好我是苏麟,今天看看二分查找相关的题目 .
大纲
- 二分查找拓展问题
- 山脉数组的峰顶索引
- 寻找旋转排序数组中的最小值
- 中序与搜索树
- 二叉搜索树中的搜索
- 验证二叉搜索树
二分查找拓展问题
山脉数组的峰顶索引
描述 :
符合下列属性的数组 arr 称为 山脉数组 ：
- arr.length >= 3
- 存在 i（0 < i < arr.length - 1）使得：
arr[0] < arr[1] < … arr[i-1] < arr[i]
arr[i] > arr[i+1] > … > arr[arr.length - 1]
给你由整数组成的山脉数组 arr ，返回满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标 i
题目 :
LeetCode 852. 山脉数组的峰顶索引
852.山脉数组的封顶索引
分析 :
这个题其实就是前面找最小值的相关过程而已，最简单的方式是对数组进行一次遍历。
解析 :
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int length = arr.length;
int n = 0;
for(int i = 0; i< length - 1;i++){
if(arr[i] > arr[i + 1]){
n = i;
break;
}
}
return n;
}
}
分析 :
使用二分来优化一下
因为此题是必为高峰数组 , 所以数组长度为 时下标1为最大值 .
解析 :
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int length = arr.length;
if(length == 3){
return 1;
}
int left = 1;
int right = length - 1;
while(left < right){
int mid = (left + right) >>> 1;
if(arr[mid - 1] < arr[mid] && arr[mid] < arr[mid + 1]){
left = mid;
}
if(arr[mid - 1] > arr[mid] && arr[mid] > arr[mid + 1]){
right = mid;
}
if(arr[mid - 1] < arr[mid] && arr[mid] > arr[mid + 1]){
return mid;
}
}
return left;
}
}
寻找旋转排序数组中的最小值
描述 :
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
- 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
- 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]]
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
题目 :
LeetCode 153. 寻找旋转排序数组中的最小值 :
153.寻找旋转排序数组中的最小值
分析 :
一个不包含重复元素的升序数组在经过旋转之后，可以得到下面可视化的折线图：
其中横轴表示数组元素的下标，纵轴表示数组元素的值。图中标出了最小值的位置，是我们需要查找的目标。
我们考虑数组中的最后一个元素 xxx ：
在最小值右侧的元素（不包括最后一个元素本身），它们的值一定都严格小于 xxx；
而在最小值左侧的元素，它们的值一定都严格大于 xxx。
因此，我们可以根据这一条性质，通过二分查找的方法找出最小值。
在二分查找的每一步中，左边界为 left，右边界为 right，区间的中点为 mid，最小值就在该区间内。我们将中轴元素 nums[mid] 与右边界元素 nums[right] 进行比较，可能会有以下的三种情况：
第一种情况是 nums[mid] > nums[right]。如下图所示，这说明 nums[mid] 是最小值右侧的元素，因此我们可以忽略二分查找区间的右半部分。
第二种情况是nums[mid] > nums[right]。如下图所示，这说明 nums[mid] 是最小值左侧的元素，因此我们可以忽略二分查找区间的左半部分。
由于数组不包含重复元素，并且只要当前的区间长度不为 1，mid 就不会与 right 重合；而如果当前的区间长度为 1，这说明我们已经可以结束二分查找了。因此不会存在nums[mid] = nums[right]的情况。
当二分查找结束时，我们就得到了最小值所在的位置。
解析 :
class Solution {
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while(left < right){
int mid = (left + right) >>> 1;
if(nums[mid] > nums[right]){
left = mid + 1;
}else{
right = mid;
}
}
return nums[left];
}
}
中序与搜索树
在前面我们发现很多题使用前序、后序或者层次遍历都可以解决，但几乎没有中序遍历的。这是因为中序与前后序相比有不一样的特征，例如中序可以和搜索树结合在一起，但是前后序则不行。
二叉搜索树是一个很简单的概念，但是想说清楚却不太容易。简单来说就是如果一棵二叉树是搜索树，则按照中序遍历其序列正好是一个递增序列。比较规范的定义是:
- 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值;
- 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值;
- 它的左、右子树也分别为二又排序树。下面这两棵树一个中序序列是 {3.6.9,10,14,16,19}，一个是{3,6,9,10}，因此都是搜索树:
搜索树的题目虽然也是用递归，但是与前后序有很大区别，主要是因为搜索树是有序的，就可以根据条件决定某些递归就不必执行了，这也称为“剪枝”。
二叉搜索树中的搜索
描述 :
给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
题目 :
LeetCode 700. 二叉搜索树中的搜索
700.二叉搜索树中的搜索
分析 :
本题看起来很复杂，但是实现非常简单，递归:
- 如果根节点为空 root == null 或者根节点的值等于搜索值 val == root.val，返回根节点
- 如果 val < root.val，进入根节点的左子树查找 searchBST(root.left, val)
- 如果 val > root.val，进入根节点的右子树查找 searchBST(root.right, val)
解析 :
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
return searchNode(root,val);
}
public TreeNode searchNode(TreeNode root,int val){
if(root == null){
return null;
}
if(root.val == val){
return root;
}else{
if(val < root.val){
root = searchBST(root.left,val);
}else{
root =searchBST(root.right,val);
}
}
return root;
}
}
分析 :
迭代方式也很简单 , 只要值不相等就循环 , 循环到最后还没有就返回null .
解析 :
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
while(root != null && root.val != val){
root = root.val > val ? root.left : root.right;
}
return root;
}
}
验证二叉搜索树
描述 :
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数
- 节点的右子树只包含 大于 当前节点的数
- 所有左子树和右子树自身必须也是二叉搜索树
题目 :
LeetCode 98. 验证二叉搜索树
验证二叉搜索树
分析 :
我们就以这个为例 :
以此代码为例讲解 :
class Solution {
public boolean isValidBST(TreeNode root) {
return is(root);
}
long pre = Long.MIN_VALUE;
public boolean is(TreeNode root){
if(root == null){
return true;
}
if(root.val <= pre){
return false;
}
pre = root.val;
return is(root.right);
}
}
第一步 :
定义变量 : long pre = Long.MIN_VALUE; 他的值为 -9223372036854775808 远远比 1 小 用来比较
第二步 :
用pre 和 root.val 比较 如果小于就返回false 否则就把root.val赋值给 pre , 最后传入节点root.right
第三步 :
以 root.right 为根节点继续比较
而下面这个代码是 递归左节点的 , 如果根节点的左节点不是二叉搜索树返回false
if(!is(root.left)){
return false;
}
解析 :
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
return is(root);
}
long pre = Long.MIN_VALUE;
public boolean is(TreeNode root){
if(root == null){
return true;
}
if(!is(root.left)){
return false;
}
if(root.val <= pre){
return false;
}
pre = root.val;
return is(root.right);
}
}
这期就到这里了 , 下期见!
