Commit7fc7125

committed

Lintcode/src/chapter2_binary_search/SearchforaRange.java

1 parentce8cc92 commit7fc7125Copy full SHA for 7fc7125

File tree

+52

-0

lines changed

+52

-0

lines changed

Lines changed: 52 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,52 @@`
	`1`	`+packagechapter2_binary_search;`
	`2`	`+`
	`3`	`+importutils.CommonUtils;`
	`4`	`+`
	`5`	`+publicclassSearchforaRange {`
	`6`	`+`
	`7`	`+/**`
	`8`	`+ *@param A : an integer sorted array`
	`9`	`+ *@param target : an integer to be inserted`
	`10`	`+ *return : a list of length 2, [index1, index2]`
	`11`	`+ */`
	`12`	`+publicstaticint[]searchRange(int[]A,inttarget) {`
	`13`	`+// write your code here`
	`14`	`+intleft =0,right =A.length-1;`
	`15`	`+int[]result =newint[]{-1, -1};`
	`16`	`+if(A ==null \|\|A.length ==0)returnresult;`
	`17`	`+while(left +1 <right){`
	`18`	`+intmid =left + (right-left)/2;`
	`19`	`+if(A[mid] ==target){`
	`20`	`+inttemp =mid;`
	`21`	`+while(temp-1 >=0 &&A[temp] ==A[temp-1])temp--;`
	`22`	`+result[0] =temp;`
	`23`	`+while(mid+1 <A.length &&A[mid] ==A[mid+1])mid++;`
	`24`	`+result[1] =mid;`
	`25`	`+returnresult;`
	`26`	`+ }elseif(A[mid] >target){`
	`27`	`+right =mid;`
	`28`	`+ }else {`
	`29`	`+left =mid;`
	`30`	`+ }`
	`31`	`+ }`
	`32`	`+if(A[left] ==target){`
	`33`	`+result[0] =left;`
	`34`	`+result[1] =left;`
	`35`	`+ }`
	`36`	`+if(A[right] ==target){`
	`37`	`+result[0] =right;`
	`38`	`+result[1] =right;`
	`39`	`+ }`
	`40`	`+returnresult;`
	`41`	`+ }`
	`42`	`+`
	`43`	`+publicstaticvoidmain(String...strings){`
	`44`	`+// int[] A = new int[]{9,10,100,101,1002,10203};`
	`45`	`+// int target = 10203;`
	`46`	`+`
	`47`	`+int[]A =newint[]{5,5,5,5,5,5,5,5,5,5};`
	`48`	`+inttarget =5;`
	`49`	`+int[]result =searchRange(A,target);`
	`50`	`+CommonUtils.printArray(result);`
	`51`	`+ }`
	`52`	`+}`

Comments

(0)