Commitea5ff4f

applewjg

committed

SearchforaRange

Change-Id: I48cb954ca9a5197f4baaf564228d515cac4b3489

1 parent368b74e commitea5ff4fCopy full SHA for ea5ff4f

File tree

+49

-0

lines changed

+49

-0

lines changed

Lines changed: 49 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,49 @@`
	`1`	`+/*`
	`2`	`+ Author: King, wangjingui@outlook.com`
	`3`	`+ Date: Dec 20, 2014`
	`4`	`+ Problem: Search for a Range`
	`5`	`+ Difficulty: Medium`
	`6`	`+ Source: https://oj.leetcode.com/problems/search-for-a-range/`
	`7`	`+ Notes:`
	`8`	`+ Given a sorted array of integers, find the starting and ending position of a given target value.`
	`9`	`+`
	`10`	`+ Your algorithm's runtime complexity must be in the order of O(log n).`
	`11`	`+`
	`12`	`+ If the target is not found in the array, return [-1, -1].`
	`13`	`+`
	`14`	`+ For example,`
	`15`	`+ Given [5, 7, 7, 8, 8, 10] and target value 8,`
	`16`	`+ return [3, 4].`
	`17`	`+`
	`18`	`+ Solution: It takes O(lgN) to find both the lower-bound and upper-bound.`
	`19`	`+ */`
	`20`	`+publicclassSolution {`
	`21`	`+publicint[]searchRange(int[]A,inttarget) {`
	`22`	`+int[]res =newint[]{-1,-1};`
	`23`	`+intlower =getLowerBound(A,target);`
	`24`	`+intupper =getUpperBound(A,target);`
	`25`	`+if (lower <=upper) {`
	`26`	`+res[0] =lower;`
	`27`	`+res[1] =upper;`
	`28`	`+ }`
	`29`	`+returnres;`
	`30`	`+ }`
	`31`	`+publicintgetLowerBound(int[]A,inttarget) {`
	`32`	`+intl =0,r =A.length -1;`
	`33`	`+while (l <=r) {`
	`34`	`+intmid = (l+r) /2;`
	`35`	`+if (A[mid] <target)l =mid +1;`
	`36`	`+elser =mid -1;`
	`37`	`+ }`
	`38`	`+returnl;`
	`39`	`+ }`
	`40`	`+publicintgetUpperBound(int[]A,inttarget) {`
	`41`	`+intl =0,r =A.length -1;`
	`42`	`+while (l <=r) {`
	`43`	`+intmid = (l+r) /2;`
	`44`	`+if (A[mid] <=target)l =mid +1;`
	`45`	`+elser =mid -1;`
	`46`	`+ }`
	`47`	`+returnr;`
	`48`	`+ }`
	`49`	`+}`

Comments

(0)