Java教程

数据结构与算法_给定数组和目标值,返回目标值位置

本文主要是介绍数据结构与算法_给定数组和目标值,返回目标值位置,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目描述:
给定一个按照升序排列的整数数组 nums,和一个目标值 target
找出给定目标值在数组中的开始位置和结束位置,如果数组中不存在目标值 target,返回 [-1, -1]
设计并实现时间复杂度为 O(log(n)) 的算法解决此问题。


编写语言Swift

func seek(numArray: [Int], target: Int) -> (Int, Int) {
	if numArray.count == 0 {
		return (-1, -1)
	}
    var min = 0, max = numArray.count - 1, first = -1, last = -1
    while min <= max {
		let mid = (max - min)/2 + min
		if numArray[mid] >= target {
			first = mid
			max = mid - 1
		} else {
			min = mid + 1
		}
	}
 	// 到此可以找到最先出现的位置, 可以以最先出现的位置为起始点开始计算最后出现的位置
	min = first
	max = numArray.count - 1
	while min <= max {
		let mid = (max - min)/2 + min
		if numArray[mid] <= target {
			last = mid
			min = mid + 1
		} else {
			max = mid - 1
		}
	}
	if numArray[first] != target {
		first = -1
	}
	return (first, last)
}
这篇关于数据结构与算法_给定数组和目标值,返回目标值位置的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!