Commitbf6a425

committed

search insert position

1 parent000093a commitbf6a425Copy full SHA for bf6a425

File tree

+35

-0

lines changed

+35

-0

lines changed

Lines changed: 35 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,35 @@`
	`1`	`+packagechapter2_binary_search;`
	`2`	`+`
	`3`	`+publicclassSearchInsertPosition {`
	`4`	`+`
	`5`	`+/**`
	`6`	`+ * param A : an integer sorted array`
	`7`	`+ * param target : an integer to be inserted`
	`8`	`+ * return : an integer`
	`9`	`+ */`
	`10`	`+publicstaticintsearchInsert(int[]A,inttarget) {`
	`11`	`+if(A ==null \|\|A.length ==0)return0;`
	`12`	`+// write your code here`
	`13`	`+intleft =0,right =A.length-1;`
	`14`	`+while(left+1 <right){`
	`15`	`+intmid =left + (right-left)/2;`
	`16`	`+if(A[mid] ==target)returnmid;`
	`17`	`+elseif(A[mid] >target)right =mid;`
	`18`	`+elseleft =mid;`
	`19`	`+ }`
	`20`	`+if(A[left] >target)returnleft ==0 ?0 :left-1;`
	`21`	`+if(A[right] <target)returnright+1;`
	`22`	`+elseif(A[left] <target)returnleft+1;`
	`23`	`+elseif(A[left] ==target)returnleft;`
	`24`	`+elsereturnright-1;`
	`25`	`+ }`
	`26`	`+`
	`27`	`+publicstaticvoidmain(String...strings){`
	`28`	`+// int[] A = new int[]{};`
	`29`	`+// int target = 9;//should be 0`
	`30`	`+`
	`31`	`+int[]A =newint[]{9,10,100,101,1002,10203};`
	`32`	`+inttarget =9;//should be 1`
	`33`	`+System.out.println(searchInsert(A,target));`
	`34`	`+ }`
	`35`	`+}`

Comments

(0)