算法题:有序数组查找目标的范围,返回下标
2022/3/19 14:57:30
本文主要是介绍算法题:有序数组查找目标的范围,返回下标,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
给定一个有序数组,在数组中找到目标值的起始和终止下标,不存在返回 [-1,-1]。
要求时间复杂度为 o(lg(n))。
例子: arr: [1,3,4,5,6,6,6,7] , target: 6;return: [4,6]
解体思路
数组有序查找,时间复杂度为 lg N,根据这两句话,很容易想到二分法。但在查找到一个元素后,不可向前向后遍历获取起始和终止下标,当数组中大部分元素相同且正好为target时,时间复杂度变为线性级别。
可以多次使用二分法查找,确定边界。
public class Search { public static void main(String[] args) { int[] arr = new int[]{1, 3, 4, 5, 6, 6, 6, 7}; int target = 6; System.out.println(Arrays.toString(search(arr, target))); } public static int[] search(int[] arr, int target) { int lt = 0; int[] res = new int[]{-1, -1}; while (lt < arr.length) { int idx = binarySearch(arr, lt, arr.length - 1, target); if (idx == -1) { break; } else { res[1] = idx; lt = idx + 1; } } int gt = arr.length - 1; while (gt > 0) { int idx = binarySearch(arr, 0, gt, target); if (idx == -1) { break; } else { res[0] = idx; gt = idx - 1; } } return res; } public static int binarySearch(int[] arr, int lo, int hi, int target) { while (lo <= hi) { int mid = (lo + hi) >>> 1; if (target > arr[mid]) { lo = mid + 1; } else if (target < arr[mid]) { hi = mid - 1; } else { return mid; } } return -1; } }
这篇关于算法题:有序数组查找目标的范围,返回下标的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?