首页 > 编程语言 > 详细

leetcode之34在排序数组中查找元素的第一个和最后一个位置Golang

时间:2020-11-15 11:03:12      阅读:24      评论:0      收藏:0      [点我收藏+]

题目描述

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值,返回 [-1, -1]

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

算法

本题采用二分法

定义高低两个指针lowhigh,另中间指针为mid=(low+high)/2,如果结果在左半部分,那么high=mid,如果结果在右半部分,那么low=mid+1,当low>=high的时候跳出循环,也有可能在中间的某个查找过程中就找到了,此时low<high

在本题中,当循环退出的时候会有两种情况:

  • low>high,那么此时结果必定是没有找到结果,也就是查找的目标不在数组中
  • low=high,那么此时的结果有可能在数组中,直接判断此时low在数组中指向的元素是不是查找的目标即可
  • 如果查找到了目标,那么只需要继续向后遍历数组,直到最后一个结果的index就可以了

代码

func searchRange(nums []int, target int) []int {
	low, high := 0, len(nums)-1
	for low < high {
		mid := (low + high) / 2
		if nums[mid] >= target {
			high = mid
		} else {
			low = mid + 1
		}
	}
	if low == high {
		//  此时有可能找到了元素
		if nums[low] == target {
			// 此时找到了这个元素,并且这是第一个元素
			index := low
			for ; index < len(nums); index++ {
				if nums[index] != target {
					break
				}
			}
			return []int{low, index - 1}
		}
	}
	return []int{-1, -1}
}

leetcode之34在排序数组中查找元素的第一个和最后一个位置Golang

原文:https://www.cnblogs.com/gyyyl/p/13975706.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!