Commit7a9a84b

piggy1991

committed

searc

1 parent81303ac commit7a9a84bCopy full SHA for 7a9a84b

File tree

+106

-0

lines changed

+106

-0

lines changed

Lines changed: 55 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,55 @@`
	`1`	`+packageAlgorithms.divide2;`
	`2`	`+`
	`3`	`+publicclassSearchRange {`
	`4`	`+publicint[]searchRange(int[]A,inttarget) {`
	`5`	`+int[]ret = {-1, -1};`
	`6`	`+if (A ==null \|\|A.length ==0) {`
	`7`	`+returnret;`
	`8`	`+ }`
	`9`	`+`
	`10`	`+intl =0;`
	`11`	`+intr =A.length -1;`
	`12`	`+`
	`13`	`+// Find the left bound.`
	`14`	`+while (l <r -1) {`
	`15`	`+intmid =l + (r -l) /2;`
	`16`	`+if (A[mid] ==target) {`
	`17`	`+r =mid;`
	`18`	`+ }elseif (A[mid] >target) {`
	`19`	`+r =mid;`
	`20`	`+ }else {`
	`21`	`+l =mid;`
	`22`	`+ }`
	`23`	`+ }`
	`24`	`+`
	`25`	`+if (A[l] ==target) {`
	`26`	`+ret[0] =l;`
	`27`	`+ }elseif (A[r] ==target) {`
	`28`	`+ret[0] =r;`
	`29`	`+ }else {`
	`30`	`+returnret;`
	`31`	`+ }`
	`32`	`+`
	`33`	`+l =0;`
	`34`	`+r =A.length -1;`
	`35`	`+// Find the right bound.`
	`36`	`+while (l <r -1) {`
	`37`	`+intmid =l + (r -l) /2;`
	`38`	`+if (A[mid] ==target) {`
	`39`	`+l =mid;`
	`40`	`+ }elseif (A[mid] >target) {`
	`41`	`+r =mid;`
	`42`	`+ }else {`
	`43`	`+l =mid;`
	`44`	`+ }`
	`45`	`+ }`
	`46`	`+`
	`47`	`+if (A[r] ==target) {`
	`48`	`+ret[1] =r;`
	`49`	`+ }else {`
	`50`	`+ret[1] =l;`
	`51`	`+ }`
	`52`	`+`
	`53`	`+returnret;`
	`54`	`+ }`
	`55`	`+}`

Lines changed: 51 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,51 @@`
	`1`	`+packageAlgorithms.sort;`
	`2`	`+`
	`3`	`+importjava.util.Arrays;`
	`4`	`+`
	`5`	`+/**`
	`6`	`+ * @author yovn`
	`7`	`+ *`
	`8`	`+ */`
	`9`	`+publicclassBucketSorter {`
	`10`	`+publicvoidsort(int[]keys,intfrom,intlen,intmax)`
	`11`	`+ {`
	`12`	`+int[]count =newint[max];`
	`13`	`+int[]tmp =newint[len];`
	`14`	`+`
	`15`	`+// count the keys.`
	`16`	`+for (inti =0;i <len;i++) {`
	`17`	`+count[keys[from +i]]++;`
	`18`	`+ }`
	`19`	`+`
	`20`	`+// calculate the position.`
	`21`	`+// BUG 1: i go from 1 not 0.`
	`22`	`+for (inti =1;i <max;i++) {`
	`23`	`+count[i] =count[i] +count[i -1];`
	`24`	`+ }`
	`25`	`+`
	`26`	`+// back the array.`
	`27`	`+System.arraycopy(keys,from,tmp,0,len);`
	`28`	`+`
	`29`	`+// Place the objects into the right position.`
	`30`	`+for (inti =len -1;i >=0;i--) {`
	`31`	`+keys[--count[tmp[i]]] =tmp[i];`
	`32`	`+ }`
	`33`	`+ }`
	`34`	`+/**`
	`35`	`+ * @param args`
	`36`	`+ */`
	`37`	`+publicstaticvoidmain(String[]args) {`
	`38`	`+`
	`39`	`+int[]a={1,4,8,3,2,9,5,0,7,6,9,10,9,13,14,15,11,12,17,16};`
	`40`	`+BucketSortersorter=newBucketSorter();`
	`41`	`+sorter.sort(a,0,a.length,20);//actually is 18, but 20 will also work`
	`42`	`+`
	`43`	`+`
	`44`	`+for(inti=0;i<a.length;i++)`
	`45`	`+ {`
	`46`	`+System.out.print(a[i]+",");`
	`47`	`+ }`
	`48`	`+`
	`49`	`+ }`
	`50`	`+`
	`51`	`+}`

Comments

(0)