def main():
    numbers = list(map(int,input().split()))
    n = len(numbers)
    target = int(input())
    numbers.sort()
    a = [0]+numbers
    l,r =1,n
    s = 'S'
    mid = (l+r)//2
    while l<=n:
        if a[mid]==target:
            s+='Y'
            break
        elif a[mid]<target:
            l = mid+1
            mid = (l+r)//2
            s+='R'
        else:
            r = mid-1
            mid = (l+r)//2
            s+='L'
    else:
        s=s[:len(s)-1]
        s+='N'
    print(s)

if __name__ == "__main__":
    main()

#include <iostream>
#include <type_traits>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int t;
    vector<int> nums;
    while (cin>>t) {
        nums.push_back(t);
    }
    int target=nums[nums.size()-1];
    nums.pop_back();
    sort(nums.begin(),nums.end());
    int l=0,r=nums.size()-1;
    string s;
    s+='S';
    while (l<=r) {
        int p=(r+l)/2;
        if (nums[p]==target) {
          s+='Y';
          cout<<s<<endl;
          return 0;
        }else if (nums[p]< target){
           l=p+1;
           s+='R';
        }else if (nums[p]> target){
           r=p-1;
           s+='L';
        }
    }
    s+='N';
    cout<<s<<endl;
}

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
    vector<int> arr;
    int a;
    while(cin>>a)
    {
        arr.push_back(a);
    }
    int target_value = arr[arr.size()-1];
    arr.pop_back();
    sort(arr.begin(), arr.end());

    int l = 1, r = arr.size();
    string s = "S";
    while(l <= r)
    {
        int p=(l+r)/2;
        if(arr[p-1]==target_value)
        {
            s += "Y";
            cout << s << endl;
            return 0;
        }
        else if(arr[p-1] < target_value)
        {
            l = p + 1;
            s += "R";
        }
        else if(arr[p-1] > target_value)
        {
            r = p - 1;
            s += "L";
        }
    }

    s += "N";
    cout << s << endl;
    return 0;
}

如果给定的序列，不是连续的，比如2 1 3 7 5 6 4 9 10 这样缺少8，还需要对序列进行排序。如果要查找的是8，按照题解是可以找到的，但是实际上是找不到的。

题面描述:

塔子哥精通二分查找，但对二叉搜索树不太了解。他手中有一棵平衡的满二叉搜索树，节点的左子树包含小于当前节点的数，右子树包含大于当前节点的数，且每个子树也符合二叉搜索树的特性。现在，塔子哥给你一个待查找的整数，请你输出查找路径及结果。输入包括两部分：第一行是 $2^n - 1$ 个整数，表示满二叉搜索树的节点值；第二行是待查找的整数。输出一个字符串，表示从根节点开始的查找路径，其中 S 表示起点，R 表示查找右子树，L 表示查找左子树，找到目标数后用 Y 表示，若未找到则用 N 表示。

思路

从根节点开始查找，标记S，待查找数8比4大,所以查找右树，标记R，8比6还大，继续查找右树标记R，8比右树节点7还大，但已经到了叶子，没有找到，因此最终标记SRRN。

模拟

题目说明给出的是一棵平衡的满二叉树，且节点个数是$2^n-1$，所以构造该二叉树的方法其实和给定的顺序无关。

假设节点个数$m=2^n-1$，编号为$1,2,...,m$。那么根节点编号就是$\lfloor{\frac{1+m}{2}}\rfloor$。之后，左子树的编号范围就变成了$[1,\lfloor{\frac{1+m}{2}}\rfloor-1]$，而右子树的范围就变成了$[\lfloor{\frac{1+m}{2}}\rfloor+1,m]$。如此往复。所以我们只需要将目标值与当前节点编号比较，并判断是走左子树还是右子树就行了。

为了模拟这一过程，我们设定子树编号范围为$L$和$R$。并在上述过程中更新$L$和$R$的值即可。

比如当前节点编号为$p$，要走左子树，那么$R=p-1$，走右子树，$L=p+1$

题解

塔子哥精通二分查找，但对二叉搜索树却不太了解。现有一棵平衡的满二叉搜索树，节点的左子树只包含小于当前节点的值，右子树只包含大于当前节点的值，并且每个子树本身也是二叉搜索树。塔子哥给你一个待查找的整数，请你输出查找路径及结果。

输入分为两部分：第一行包含 $2^n - 1$ 个整数，表示整棵满二叉搜索树的节点值；第二行包含一个待查找的整数。输出一个字符串，表示从根节点开始的查找路径。路径中的符号定义如下：

• S 表示起点（根节点）。
• L 表示查找左子树。
• R 表示查找右子树。
• Y 表示找到目标数。
• N 表示未找到目标数。

代码逻辑分析

1. 输入处理：通过循环读取输入的节点值，直到没有输入为止，将每个值存储在数组 a 中。
2. 目标数设定：在读取完成后，最后一个输入值被设定为待查找的目标数。
3. 查找路径构建：
   • 初始化路径字符串为 S，表示从根节点开始。
   • 使用变量 l 和 r 分别表示当前查找区间的左边界和右边界，初始时为整棵树的边界。
   • 使用 p 来表示当前查找的节点值，初始时为根节点。
   • 在每次比较中，如果目标数小于当前节点值，更新右边界并查找左子树，路径添加 L；如果目标数大于当前节点值，更新左边界并查找右子树，路径添加 R。
4. 查找结果：当找到目标数后，路径字符串添加 Y，表示找到目标数并输出。

代码

Python

import sys

# 定义常量，最大元素数量
MAXN = 10010
a = [0] * MAXN  # 数组用于存储输入的数据
n = 0  # 当前输入的元素个数

def main():
    global n  # 使用全局变量n
    
    # 读取输入的整数到数组中
    for line in sys.stdin:
        # 将每行输入的整数添加到数组a中
        numbers = list(map(int, line.split()))
        for number in numbers:
            a[n] = number
            n += 1
    
    n -= 1  # 调整n，指向最后一个有效元素
    target = a[n]  # 目标值是最后一个输入的整数
    s = "S"  # 初始化路径字符串，起始为"S"
    
    l = 1  # 初始化左边界
    r = n  # 初始化右边界
    p = (l + r) // 2  # 初始化中间位置
    
    # 二分查找
    while p != target:
        if target < p:
            r = p - 1  # 如果目标小于中间值，右边界调整
            p = (l + r) // 2  # 重新计算中间位置
            s += "L"  # 路径中加入"L"
        else:
            l = p + 1  # 如果目标大于中间值，左边界调整
            p = (l + r) // 2  # 重新计算中间位置
            s += "R"  # 路径中加入"R"
    
    s += "Y"  # 找到目标后，路径中加入"Y"
    print(s)  # 输出路径

if __name__ == "__main__":
    main()

Java

import java.util.Scanner;

public class Main { // 修改为 Main 类
    // 定义常量，最大元素数量
    private static final int MAXN = 10010;
    private static int[] a = new int[MAXN]; // 数组用于存储输入的数据
    private static int n = 0; // 当前输入的元素个数

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入的整数到数组中
        while (scanner.hasNextInt()) {
            a[n++] = scanner.nextInt();
        }
        
        n--; // 调整n，指向最后一个有效元素
        int target = a[n]; // 目标值是最后一个输入的整数
        StringBuilder s = new StringBuilder("S"); // 初始化路径字符串，起始为"S"
        
        int l = 1, r = n; // 初始化左右边界
        int p = (l + r) / 2; // 初始化中间位置
        
        // 二分查找
        while (p != target) {
            if (target < p) {
                r = p - 1; // 如果目标小于中间值，右边界调整
                p = (l + r) / 2; // 重新计算中间位置
                s.append("L"); // 路径中加入"L"
            } else {
                l = p + 1; // 如果目标大于中间值，左边界调整
                p = (l + r) / 2; // 重新计算中间位置
                s.append("R"); // 路径中加入"R"
            }
        }
        
        s.append("Y"); // 找到目标后，路径中加入"Y"
        System.out.println(s.toString()); // 输出路径
        
        scanner.close(); // 关闭输入扫描器
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

const int maxn=1e4+10;
int a[maxn],n;

int main(){
	std::ios::sync_with_stdio(false);
	while(cin>>a[n]){
		n++;
	}
	n--;
	int target=a[n];
	string s="S";
	int p=(1+n)/2;
	int l=1,r=n;
	while(p!=target){
		if(target<p){
			r=p-1;
			p=(l+p-1)/2;
			s+="L";
		}else{
			l=p+1;
			p=(p+1+r)/2;
			s+='R';
		}
	}
	s+="Y";
	cout<<s;
	
	return 0;
}