Commit75dd8a2

committed

0704: Binary Search

1 parent40960d2 commit75dd8a2Copy full SHA for 75dd8a2

File tree

+115

-0

lines changed

+115

-0

lines changed

Lines changed: 43 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,43 @@`
	`1`	`+constnums=[-1,0,3,5,9,12];`
	`2`	`+consttarget1=9;`
	`3`	`+consttarget2=2;`
	`4`	`+functionsearchUsingLCRC(nums,target){`
	`5`	`+letmid,left=0,right=nums.length-1;`
	`6`	`+while(left<=right){`
	`7`	`+mid=left+((right-left)>>1);`
	`8`	`+if(nums[mid]>target){`
	`9`	`+right=mid-1;`
	`10`	`+}`
	`11`	`+elseif(nums[mid]<target){`
	`12`	`+left=mid+1;`
	`13`	`+}`
	`14`	`+else{`
	`15`	`+returnmid;`
	`16`	`+}`
	`17`	`+}`
	`18`	`+return-1;`
	`19`	`+}`
	`20`	`+functionsearchUsingLCRO(nums,target){`
	`21`	`+letmid,left=0,right=nums.length;`
	`22`	`+while(left<right){`
	`23`	`+mid=left+((right-left)>>1);`
	`24`	`+if(nums[mid]>target){`
	`25`	`+right=mid;`
	`26`	`+}`
	`27`	`+elseif(nums[mid]<target){`
	`28`	`+left=mid+1;`
	`29`	`+}`
	`30`	`+else{`
	`31`	`+returnmid;`
	`32`	`+}`
	`33`	`+}`
	`34`	`+return-1;`
	`35`	`+}`
	`36`	`+console.time("searchUsingLCRC");`
	`37`	`+searchUsingLCRC(nums,target1);`
	`38`	`+console.timeEnd("searchUsingLCRC");`
	`39`	`+console.time("searchUsingLCRO");`
	`40`	`+searchUsingLCRO(nums,target1);`
	`41`	`+console.timeEnd("searchUsingLCRO");`
	`42`	`+console.log(searchUsingLCRC(nums,target1));`
	`43`	`+console.log(searchUsingLCRO(nums,target1));`

Lines changed: 50 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,50 @@`
	`1`	`+constnums=[-1,0,3,5,9,12]`
	`2`	`+consttarget1=9`
	`3`	`+consttarget2=2`
	`4`	`+`
	`5`	`+functionsearchUsingLCRC(nums:number[],target:number):number{`
	`6`	`+letmid:number,`
	`7`	`+left:number=0,`
	`8`	`+right:number=nums.length-1`
	`9`	`+`
	`10`	`+while(left<=right){`
	`11`	`+mid=left+((right-left)>>1)`
	`12`	`+if(nums[mid]>target){`
	`13`	`+right=mid-1`
	`14`	`+}elseif(nums[mid]<target){`
	`15`	`+left=mid+1`
	`16`	`+}else{`
	`17`	`+returnmid`
	`18`	`+}`
	`19`	`+}`
	`20`	`+`
	`21`	`+return-1`
	`22`	`+}`
	`23`	`+`
	`24`	`+functionsearchUsingLCRO(nums:number[],target:number):number{`
	`25`	`+letmid:number,`
	`26`	`+left:number=0,`
	`27`	`+right:number=nums.length`
	`28`	`+while(left<right){`
	`29`	`+mid=left+((right-left)>>1)`
	`30`	`+if(nums[mid]>target){`
	`31`	`+right=mid`
	`32`	`+}elseif(nums[mid]<target){`
	`33`	`+left=mid+1`
	`34`	`+}else{`
	`35`	`+returnmid`
	`36`	`+}`
	`37`	`+}`
	`38`	`+return-1`
	`39`	`+}`
	`40`	`+`
	`41`	`+console.time("searchUsingLCRC")`
	`42`	`+searchUsingLCRC(nums,target1)`
	`43`	`+console.timeEnd("searchUsingLCRC")`
	`44`	`+`
	`45`	`+console.time("searchUsingLCRO")`
	`46`	`+searchUsingLCRO(nums,target1)`
	`47`	`+console.timeEnd("searchUsingLCRO")`
	`48`	`+`
	`49`	`+console.log(searchUsingLCRC(nums,target1))`
	`50`	`+console.log(searchUsingLCRO(nums,target1))`

Lines changed: 22 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,22 @@`
	`1`	+Given an array of integers`nums` which is sorted in ascending order, and an integer`target`, write a function to search`target` in`nums`. If`target` exists, then return its index. Otherwise, return`-1`.
	`2`	`+`
	`3`	+You must write an algorithm with`O(log n)` runtime complexity.
	`4`	`+`
	`5`	`+Example 1:`
	`6`	`+`
	`7`	`+><spanstyle="color:white;">Input</span>: nums =[-1,0,3,5,9,12], target = 9<br>`
	`8`	`+><spanstyle="color:white;">Output</span>: 4<br>`
	`9`	`+><spanstyle="color:white;">Explanation</span>: 9 exists in nums and its index is 4`
	`10`	`+`
	`11`	`+Example 2:`
	`12`	`+`
	`13`	`+><spanstyle="color:white;">Input</span>: nums =[-1,0,3,5,9,12], target = 2<br>`
	`14`	`+><spanstyle="color:white;">Output</span>: -1<br>`
	`15`	`+><spanstyle="color:white;">Explanation</span>: 2 does not exist in nums so return -1`
	`16`	`+`
	`17`	`+Constraints:`
	`18`	`+`
	`19`	`+- 1 <= nums.length <= 10<sup>4</sup>`
	`20`	`+- -10<sup>4</sup> < nums[i], target < 10<sup>4</sup>`
	`21`	+- All the integers in`nums` are unique.
	`22`	+-`nums` is sorted in ascending order.

Comments

(0)