Question
Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1]
.
For example,
Given [5, 7, 7, 8, 8, 10]
and target value 8,
return [3, 4]
.
Solution
Use binary search, first, find left position, then, find right position.
public class Solution {
public int[] searchRange(int[] nums, int target) {
int[] result = new int[2];
result[0] = -1;
result[1] = -1;
if (nums == null || nums.length < 1)
return result;
int start = 0, end = nums.length - 1, mid, first, last;
// Find first position of target
while (start + 1 < end) {
mid = (end - start) / 2 + start;
if (nums[mid] >= target)
end = mid;
else
start = mid;
}
if (nums[start] == target)
result[0] = start;
else if (nums[end] == target)
result[0] = end; // Find last position of target
start = 0;
end = nums.length - 1;
while (start + 1 < end) {
mid = (end - start) / 2 + start;
if (nums[mid] <= target)
start = mid;
else
end = mid;
}
if (nums[end] == target)
result[1] = end;
else if (nums[start] == target)
result[1] = start;
return result;
}
}
Search for a Range 解答的更多相关文章
-
Add Digits, Maximum Depth of BinaryTree, Search for a Range, Single Number,Find the Difference
最近做的题记录下. 258. Add Digits Given a non-negative integer num, repeatedly add all its digits until the ...
-
LeetCode:Search Insert Position,Search for a Range (二分查找,lower_bound,upper_bound)
Search Insert Position Given a sorted array and a target value, return the index if the target is fo ...
-
[OJ] Search for a Range
LintCode 61. Search for a Range (Medium) LeetCode 34. Search for a Range (Medium) class Solution { p ...
-
[LeetCode] 034. Search for a Range (Medium) (C++/Java)
索引:[LeetCode] Leetcode 题解索引 (C++/Java/Python/Sql) Github: https://github.com/illuz/leetcode 035. Sea ...
-
[Leetcode][Python]34: Search for a Range
# -*- coding: utf8 -*-'''__author__ = 'dabay.wang@gmail.com' 34: Search for a Rangehttps://oj.leetco ...
-
leetCode 34.Search for a Range (搜索范围) 解题思路和方法
Search for a Range Given a sorted array of integers, find the starting and ending position of a give ...
-
Leetcode::Longest Common Prefix &;&; Search for a Range
一次总结两道题,两道题目都比较基础 Description:Write a function to find the longest common prefix string amongst an a ...
-
[array] leetcode - 34. Search for a Range - Medium
leetcode - 34. Search for a Range - Medium descrition Given an array of integers sorted in ascending ...
-
【LeetCode】34. Search for a Range
Search for a Range Given a sorted array of integers, find the starting and ending position of a give ...
随机推荐
-
kafka源码分析之二客户端分析
客户端由两种:生产者和消费者 1. 生产者 先看一下生产者的构造方法: private KafkaProducer(ProducerConfig config, Serializer<K> ...
-
.pop ----remove 删除
s = {1,2,3,4,5,6,'sn','7'} s.pop()#删除随机值 print(s)#{2, 3, 4, 5, 6, '7', 'sn'} s.remove('sn')#删除值 prin ...
-
区间重叠计算及IntervalTree初识
最近被人问到这样一个问题的解决方案:在一个餐馆的预定系统中,接受用户在未来任意一段时间内的预订用餐,用户在预订的时候需要提供用餐的开始时间和结束,餐馆的餐桌是用限的,问题是,系统要在最快的时间段计算出 ...
-
浅谈EasyUI---C#三层架构---
每次写博客,第一句话都是这样的:程序员很苦逼,除了会写程序,还得会写博客!当然,希望将来的一天,某位老板看到此博客,给你的程序员职工加点薪资吧!因为程序员的世界除了苦逼就是沉默.我眼中的程序员大多都不 ...
-
利用HttpWebRequest访问WebApi
WebApi现在越来越流行,下面给出利用HttpWebRequest访问WebApi的工具方法: 1.利用基准URL和参数字典生成完整URL /// <summary> /// 生成URL ...
-
Jquery JSOPN在WebApi中的问题
1. 客户端代码: $.ajax({ data: { name: 'zhangsan' }, url: apiUrl.getTwo('TestFourth'), dataType: 'jsonp', ...
-
C++中的随机数函数(
标签:ul 随机数 c 整数 max 教育 C++中产生随机数种子对于刚開始学习的人一直都非常困惑.大家知道,在C中有专门的srand(N)函数能够轻松实现这一功能,然而在C++中则要复杂一些.以下 ...
-
check————身份证
-- Access 不支持 Substring 查询,可以替换为 mid 查询. select 序号,姓名,身份证号,性别from 身份表where (len(身份证号)<>15 and ...
-
knockout中viewmodel跟子model相互调用
用knockout写前端复杂js逻辑的确很方便,而且html界面也很清爽. 在ko中对于复杂的业务逻辑我会给viewmodel创建一些子model对象,但是viewmodel跟子model怎样相互调用 ...
-
Android Studio 错误 Duplicate files copied in APK META-INF/LICENSE.txt解决方案
My logcat: log Execution failed for task ':Prog:packageDebug'. Duplicate files copied in APK META-IN ...