NOIP2026复赛二分答案与二分查找专项训练题

NOIP2026复赛二分答案与二分查找专项训练题第一部分：二分查找基础应用（共3题，每题10分）题目1（10分）：问题描述：给定一个严格递增的整数数组`nums`和一个目标值`target`，请实现二分查找算法，找出`target`在数组中的位置（从0开始计数）。如果`target`不存在于数组中，返回`-1`。输入格式：第一行输入一个整数`n`（数组长度），第二行输入`n`个严格递增的整数，第三行输入一个目标整数`target`。输出格式：输出`target`在数组中的位置，如果不存在则输出`-1`。示例输入：5135795示例输出：2题目2（10分）：问题描述：在一个由`n`个正整数组成的严格递增数组`arr`中，存在大量重复元素。请设计二分查找算法，找出第一个不小于`target`的元素的位置（从0开始计数）。如果所有元素都小于`target`，返回`n`。输入格式：第一行输入一个整数`n`（数组长度），第二行输入`n`个严格递增的整数，第三行输入一个正整数`target`。输出格式：输出第一个不小于`target`的元素的位置，如果不存在则输出`n`。示例输入：712233343示例输出：3题目3（10分）：问题描述：给定一个严格递增的整数数组`nums`，和一个整数`k`。请判断是否存在两个不同的下标`i`和`j`（`0<=i<j<n`），使得`nums[i]+nums[j]==k`。如果存在，返回`true`；否则返回`false`。输入格式：第一行输入一个整数`n`（数组长度），第二行输入`n`个严格递增的整数，第三行输入一个整数`k`。输出格式：输出`true`或`false`。示例输入：412453示例输出：true第二部分：二分查找进阶应用（共3题，每题15分）题目4（15分）：问题描述：给定一个包含`n`个正整数的数组`arr`，数组已经按严格递增排序。请设计二分查找算法，找出数组中最接近`target`的元素的位置（从0开始计数）。如果有两个元素与`target`的距离相同，返回较小的那个位置。如果`target`小于数组中的最小元素，返回`0`；如果`target`大于数组中的最大元素，返回`n-1`。输入格式：第一行输入一个整数`n`（数组长度），第二行输入`n`个严格递增的整数，第三行输入一个正整数`target`。输出格式：输出最接近`target`的元素的位置。示例输入：613579116示例输出：2题目5（15分）：问题描述：在一个由`n`个正整数组成的严格递增数组`arr`中，可能存在重复元素。请设计二分查找算法，找出`target`在数组中的最左边界位置（即第一个等于`target`的位置）。如果`target`不存在于数组中，返回`-1`。输入格式：第一行输入一个整数`n`（数组长度），第二行输入`n`个严格递增的整数，第三行输入一个正整数`target`。输出格式：输出`target`在数组中的最左边界位置，如果不存在则输出`-1`。示例输入：8122234452示例输出：1题目6（15分）：问题描述：给定一个由`n`个正整数组成的严格递增数组`arr`，和一个整数`k`。请设计二分查找算法，找出数组中所有和为`k`的连续子数组的个数。如果不存在，返回`0`。输入格式：第一行输入一个整数`n`（数组长度），第二行输入`n`个严格递增的整数，第三行输入一个整数`k`。输出格式：输出和为`k`的连续子数组的个数。示例输入：5123455示例输出：2第三部分：二分查找与动态规划结合（共3题，每题20分）题目7（20分）：问题描述：给定一个由`n`个正整数组成的严格递增数组`arr`，和一个整数`k`。请设计二分查找算法，找出所有满足`arr[i]+arr[j]<=k`的连续子数组的个数。如果不存在，返回`0`。输入格式：第一行输入一个整数`n`（数组长度），第二行输入`n`个严格递增的整数，第三行输入一个整数`k`。输出格式：输出满足条件的连续子数组的个数。示例输入：612345610示例输出：6题目8（20分）：问题描述：给定一个由`n`个正整数组成的严格递增数组`arr`，和一个整数`m`。请设计二分查找算法，找出所有满足`arr[i]+arr[j]+arr[k]<=m`的连续子数组的个数。如果不存在，返回`0`。输入格式：第一行输入一个整数`n`（数组长度），第二行输入`n`个严格递增的整数，第三行输入一个整数`m`。输出格式：输出满足条件的连续子数组的个数。示例输入：5123459示例输出：4题目9（20分）：问题描述：给定一个由`n`个正整数组成的严格递增数组`arr`，和一个整数`k`。请设计二分查找算法，找出所有满足`arr[i]+arr[j]+arr[l]==k`的连续子数组的个数。如果不存在，返回`0`。输入格式：第一行输入一个整数`n`（数组长度），第二行输入`n`个严格递增的整数，第三行输入一个整数`k`。输出格式：输出满足条件的连续子数组的个数。示例输入：7123456710示例输出：1答案与解析第一部分：二分查找基础应用题目1：答案：pythondefbinary_search(nums,target):left,right=0,len(nums)-1whileleft<=right:mid=(left+right)//2ifnums[mid]==target:returnmidelifnums[mid]<target:left=mid+1else:right=mid-1return-1示例输入n=5nums=[1,3,5,7,9]target=5print(binary_search(nums,target))#输出：2解析：二分查找的基本思想是在严格递增的数组中，通过不断将搜索区间减半来快速定位目标值。具体步骤如下：1.初始化左右指针`left`和`right`，分别指向数组的起始和结束位置。2.在`left<=right`的条件下，计算中间位置`mid`。3.如果`nums[mid]==target`，返回`mid`。4.如果`nums[mid]<target`，说明目标值在右侧，将`left`更新为`mid+1`。5.如果`nums[mid]>target`，说明目标值在左侧，将`right`更新为`mid-1`。6.如果循环结束仍未找到目标值，返回`-1`。题目2：答案：pythondeffirst_not_less(nums,target):left,right=0,len(nums)whileleft<right:mid=(left+right)//2ifnums[mid]<target:left=mid+1else:right=midreturnleft示例输入n=7nums=[1,2,2,3,3,3,4]target=3print(first_not_less(nums,target))#输出：3解析：与普通二分查找的区别在于，当`nums[mid]<target`时，目标值可能在右侧，因此将`left`更新为`mid+1`；否则，将`right`更新为`mid`。这样可以在找到第一个不小于`target`的元素时停止。如果所有元素都小于`target`，`left`会指向`n`。题目3：答案：pythondeftwo_sum(nums,k):left,right=0,len(nums)-1whileleft<right:ifnums[left]+nums[right]==k:returnTrueelifnums[left]+nums[right]<k:left+=1else:right-=1returnFalse示例输入n=4nums=[1,2,4,5]k=3print(two_sum(nums,k))#输出：True解析：双指针法。初始化两个指针`left`和`right`，分别指向数组的起始和结束位置。1.如果`nums[left]+nums[right]==k`，返回`true`。2.如果`nums[left]+nums[right]<k`，说明需要更大的和，将`left`向右移动。3.如果`nums[left]+nums[right]>k`，说明需要更小的和，将`right`向左移动。4.如果循环结束仍未找到，返回`false`。第二部分：二分查找进阶应用题目4：答案：pythondefclosest_element(nums,target):left,right=0,len(nums)-1closest=0min_diff=float('inf')whileleft<=right:mid=(left+right)//2diff=abs(nums[mid]-target)ifdiff<min_diff:min_diff=diffclosest=midifnums[mid]<target:left=mid+1elifnums[mid]>target:right=mid-1else:returnmidreturnclosest示例输入n=6nums=[1,3,5,7,9,11]target=6print(closest_element(nums,target))#输出：2解析：在普通二分查找的基础上，记录当前最接近`target`的元素位置。每次计算中间元素与`target`的差值，如果更小则更新最接近的位置。如果找到完全相等的元素，直接返回该位置。如果`target`小于最小元素，返回`0`；如果大于最大元素，返回`n-1`。题目5：答案：pythondeffirst_occurrence(nums,target):left,right=0,len(nums)-1result=-1whileleft<=right:mid=(left+right)//2ifnums[mid]==target:result=midright=mid-1elifnums[mid]<target:left=mid+1else:right=mid-1returnresult示例输入n=8nums=[1,2,2,2,3,4,4,5]target=2print(first_occurrence(nums,target))#输出：1解析：在普通二分查找的基础上，当找到`target`时，不立即返回，而是将`right`更新为`mid-1`，继续在左侧查找是否存在更早的`target`。这样可以确保找到最左边界的位置。如果循环结束仍未找到，返回`-1`。题目6：答案：pythondefcount_subarrays_with_sum(nums,k):n=len(nums)count=0foriinrange(n):current_sum=0forjinrange(i,n):current_sum+=nums[j]ifcurrent_sum==k:count+=1returncount示例输入n=5nums=[1,2,3,4,5]k=5print(count_subarrays_with_sum(nums,k))#输出：2解析：暴力枚举所有可能的连续子数组，并统计和为`k`的个数。对于每个起始位置`i`，累加到结束位置`j`的和，如果等于`k`则计数加1。时间复杂度为`O(n^2)`，适用于小规模数据。第三部分：二分查找与动态规划结合题目7：答案：pythondefcount_subarrays_less_than_k(nums,k):n=len(nums)count=0foriinrange(n):min_sum=float('inf')forjinrange(i,n):min_sum=min(min_sum,nums[j])ifmin_sum+nums[i]<=k:count+=1else:breakreturncount示例输入n=6nums=[1,2,3,4,5,6]k=10print(count_subarrays_less_than_k(nums,k))#输出：6解析：对于每个起始位置`i`，维护一个最小和`min_sum`，从`i`开始向右扩展，每次更新`min_sum`，如果`min_sum+nums[i]<=k`则计数加1，否则停止扩展。时间复杂度为`O(n^2)`，适用于小规模数据。题目8：答案：pythondefcount_triplets_less_than_m(nums,m):n=len(nums)count=0foriinrange(n):left,right=i+1,n-1whileleft<right:current_sum=nums[i]+nums[left]+nums[right]ifcurrent_sum<=m:count+=right-leftleft+=1else:right-=1returncount示例输入n=5nums=[1,2,3,4,5]m=9print(count_triplets_less_than_m(nums,m))#输出：4解析：对于每个起始位置`i`，使用双指针`left`和`right`在剩余数组中寻找满足条件的`nums[left]+nums[right]`。如果`nums[i]+nums[left]+nums[right]<=m`，