【数据结构】算法 排序数组中查找元素的第一个和最后一个位置 Find First And Last Position of Element in Sorted Array
2021/10/13 14:15:03
本文主要是介绍【数据结构】算法 排序数组中查找元素的第一个和最后一个位置 Find First And Last Position of Element in Sorted Array,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录- 排序数组中查找元素的第一个和最后一个位置 Find First And Last Position of Element in Sorted Array
- 思路
- Tag
排序数组中查找元素的第一个和最后一个位置 Find First And Last Position of Element in Sorted Array
给定一个非递减排序数组nums
和目标target
.找到target在数组中的开始位置和结束位置。如果数组中不存在这个数,返回[-1,-1]
nums = [5,7,7,8,8,10], target = 7 [1,2]
思路
这个要求,查到target的第一个位置和最后一个位置。
如何查第一个位置?
因为是有序的,可以通过二分查找来定位。
如何查找最后一个位置?
因为是有序的,在二分查找中,设定l,r逼近目标mid,返回最后一个位置。
public int[] searchRange(int[] nums, int target) { int[] ans = new int[]{-1,-1}; int pos = 0; int first = searchfirst01(nums,pos, target); if(first==nums.length||nums[first]!=target){ return ans; } pos = first; int last = searchfirst01(nums, pos,target+1)-1; ans[0] = first; ans[1] = last; return ans; } public int searchfirst01(int[] arr,int pos, int target){ if(arr.length==0){ return -1; } int l = pos ; int r = arr.length-1; int mid = 0; while (r-l>3){ mid = (l+r)>>1; if(arr[mid]>=target){ r = mid; } else{ l =mid+1; } } for (int i = l; i <=r ; i++) { if (arr[i]>=target){ return i; } } return arr.length; }
searchfirst01 用来寻找数组中满足 x>=target的第一个位置,如果是target==7,就返回第一个位置;要想定位最后一个位置,就尝试寻找第一个x>=8的位置,然后-1;如果找不到满足条件的位置,就返回数组长度
Tag
math
binary search
这篇关于【数据结构】算法 排序数组中查找元素的第一个和最后一个位置 Find First And Last Position of Element in Sorted Array的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)