Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit6f82c58

Browse files
refactor: js - binary search (neetcode-gh#464)
Co-authored-by: Mitchell Irvin <16233245+mitchellirvin@users.noreply.github.com>
1 parentf7683d1 commit6f82c58

7 files changed

+179
-214
lines changed
Lines changed: 19 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,17 +1,25 @@
11
/**
22
*@param {number[]} nums
3+
* Time O(log(N)) | Space O(1)
34
*@return {number}
45
*/
5-
varfindMin=function(nums){
6-
letleft=0;
7-
letright=nums.length-1;
8-
while(right>left){
9-
letmid=Math.floor((right+left)/2);
10-
if(nums[mid]>nums[right]){
11-
left=mid+1;
12-
}else{
13-
right=mid;
14-
}
6+
varfindMin=function(nums){
7+
let[left,right]=[0,(nums.length-1)];
8+
9+
while(left<right){
10+
constmid=(left+right)>>1;
11+
constguess=nums[mid];
12+
const[leftNum,rightNum]=[nums[left],nums[right]];
13+
14+
constisTarget=leftNum<rightNum;
15+
if(isTarget)returnleftNum;
16+
17+
constisTargetGreater=leftNum<=guess;
18+
if(isTargetGreater)left=mid+1;
19+
20+
constisTargetLess=guess<leftNum;
21+
if(isTargetLess)right=mid;
1522
}
23+
1624
returnnums[left];
17-
};
25+
};

‎javascript/33-Search-in-Rotated-Sorted-Array.js

Lines changed: 29 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -1,39 +1,42 @@
11
/**
22
*@param {number[]} nums
33
*@param {number} target
4+
* Time O(log(N)) | Space O(1)
45
*@return {number}
56
*/
6-
varsearch=function(nums,target){
7-
letleft=0;
8-
letright=nums.length-1;
9-
7+
varsearch=(nums,target)=>{
8+
let[left,right]=[0,nums.length-1];
9+
1010
while(left<=right){
11-
letmid=Math.floor((left+right)/2);
11+
constmid=(left+right)>>1;
12+
constguess=nums[mid];
13+
const[leftNum,rightNum]=[nums[left],nums[right]];
1214

13-
if(nums[mid]===target){
14-
returnmid;
15-
}
15+
constisTarget=guess===target;
16+
if(isTarget)returnmid;
17+
18+
constisAscending=leftNum<=guess;
19+
if(isAscending){
20+
constisInRange=leftNum<=target;
21+
constisLess=target<guess;
1622

17-
// Checking if the left side is sorted
18-
if(nums[left]<=nums[mid]){
19-
if(nums[left]<=target&&target<=nums[mid]){
20-
// thus target is in the left
21-
right=mid-1;
22-
}else{
23-
// thus target is in the right
24-
left=mid+1;
25-
}
23+
constisTargetGreater=!(isInRange&&isLess);
24+
if(isTargetGreater)left=mid+1;
25+
26+
constisTargetLess=isInRange&&isLess;
27+
if(isTargetLess)right=mid-1;
2628
}
2729

28-
// Otherwise, the right side is sorted
29-
else{
30-
if(nums[mid]<=target&&target<=nums[right]){
31-
// thus target is in the right
32-
left=mid+1;
33-
}else{
34-
// thus target is in the left
35-
right=mid-1;
36-
}
30+
constisDescending=guess<leftNum;
31+
if(isDescending){
32+
constisGreater=guess<target;
33+
constisInRange=target<=rightNum;
34+
35+
constisTargetGreater=isGreater&&isInRange;
36+
if(isTargetGreater)left=mid+1;
37+
38+
constisTargetLess=!(isGreater&&isInRange);
39+
if(isTargetLess)right=mid-1;
3740
}
3841
}
3942

Lines changed: 39 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -1,34 +1,48 @@
11
/**
22
*@param {number[]} nums1
33
*@param {number[]} nums2
4+
* Time O(log(N * M)) | Space O(N)
45
*@return {number}
56
*/
6-
varfindMedianSortedArrays=function(nums1,nums2){
7-
let[A,B]=[nums1,nums2];
8-
consttotal=nums1.length+nums2.length;
9-
consthalf=Math.floor(total/2);
7+
varfindMedianSortedArrays=function(nums1,nums2){
8+
constcanSwap=nums2.length<nums1.length;
9+
if(canSwap)[nums1,nums2]=[nums2,nums1];
1010

11-
if(B.length<A.length){
12-
[A,B]=[B,A];
13-
}
11+
let[left,right]=[0,nums1.length-1];
12+
consttotalLength=nums1.length+nums2.length
13+
constmid=totalLength>>1;
14+
constisEven=(totalLength%2)===0;
1415

15-
let[l,r]=[0,A.length-1];
1616
while(true){
17-
consti=l+r;
18-
constj=half-i-2;
19-
20-
constAleft=i>=0 ?A[i] :-Infinity;
21-
constAright=i+1<A.length ?A[i+1] :Infinity;
22-
constBleft=j>=0 ?B[j] :-Infinity;
23-
constBright=j+1<B.length ?B[j+1] :Infinity;
24-
25-
if(Aleft<=Bright&&Bleft<=Aright){
26-
if(total%2){
27-
returnMath.min(Aright,Bright);
28-
}
29-
30-
return(Math.max(Aleft,Bleft)+Math.min(Aright,Bright))/2;
31-
}elseif(Aleft>Bright)r=i-1;
32-
elsel=i+1;
17+
constmid1=left+right;
18+
constmid2=(mid-mid1)-2;
19+
const{ aLeft, aRight, bLeft, bRight}=getPointers(nums1,mid1,nums2,mid2);
20+
21+
constisTarget=(aLeft<=bRight)&&(bLeft<=aRight);
22+
if(isTarget)returnisEven
23+
?(Math.max(aLeft,bLeft)+Math.min(aRight,bRight))/2
24+
:Math.min(aRight,bRight);
25+
26+
constisTargetGreater=aLeft<=bRight;
27+
if(isTargetGreater)left=mid1+1;
28+
29+
constisTargetLess=bRight<aLeft;
30+
if(isTargetLess)right=mid1-1;
3331
}
34-
};
32+
}
33+
34+
constgetPointers=(nums1,mid1,nums2,mid2)=>{
35+
constgetLeft=(nums,index)=>0<=index
36+
?nums[index]
37+
:-Infinity;
38+
39+
const[aLeft,bLeft]=[getLeft(nums1,mid1),getLeft(nums2,mid2)];
40+
41+
constgetRight=(nums,index)=>(index+1)<nums.length
42+
?nums[index+1]
43+
:Infinity;
44+
45+
const[aRight,bRight]=[getRight(nums1,mid1),getRight(nums2,mid2)];
46+
47+
return{ aLeft, aRight, bLeft, bRight};
48+
}

‎javascript/704-Binary-Search.js

Lines changed: 13 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1,26 +1,25 @@
11
/**
22
*@param {number[]} nums
33
*@param {number} target
4+
* Time O(log(N)) | Space O(1)
45
*@return {number}
56
*/
6-
varsearch=function(nums,target){
7-
letleft=0;
8-
letright=nums.length-1;
7+
varsearch=function(nums,target){
8+
let[left,right]=[0,(nums.length-1)];
99

1010
while(left<=right){
11-
letmiddle=Math.floor((left+right)/2);
11+
constmid=(left+right)>>1;
12+
constguess=nums[mid];
1213

13-
if(nums[middle]===target){
14-
returnmiddle;
15-
}elseif(nums[middle]<target){
16-
left=middle+1;
17-
}else{
18-
right=middle-1;
19-
}
14+
constisTarget=guess===target;
15+
if(isTarget)returnmid;
16+
17+
constisTargetGreater=guess<target;
18+
if(isTargetGreater)left=mid+1;
19+
20+
constisTargetLess=target<guess;
21+
if(isTargetLess)right=mid-1;
2022
}
2123

2224
return-1;
2325
};
24-
25-
// Runtime: 98 ms, faster than 34.02% of JavaScript online submissions for Binary Search.
26-
// Memory Usage: 44.3 MB, less than 99.18% of JavaScript online submissions for Binary Search.

‎javascript/74-Search-A-2D-Matrix.js

Lines changed: 14 additions & 79 deletions
Original file line numberDiff line numberDiff line change
@@ -1,92 +1,27 @@
1-
//////////////////////////////////////////////////////////////////////////////
2-
// Single Binary Search
3-
// Time: O(log(mn)) Space: O(1)
4-
//////////////////////////////////////////////////////////////////////////////
5-
61
/**
72
*@param {number[][]} matrix
83
*@param {number} target
4+
* Time O(log(ROWS * COLS)) | Space O(1)
95
*@return {boolean}
106
*/
11-
functionsearchMatrix(matrix,target){
12-
constwidth=matrix[0].length;
13-
constheight=matrix.length;
14-
leti=0;
15-
letj=height*width-1;
16-
17-
while(i<=j){
18-
constm=Math.floor((i+j)/2);
19-
constr=Math.floor(m/width);
20-
constc=m%width;
21-
22-
if(matrix[r][c]===target){
23-
returntrue;
24-
}
25-
26-
if(matrix[r][c]<target){
27-
i=m+1;
28-
}else{
29-
j=m-1;
30-
}
31-
}
7+
varsearchMatrix=function(matrix,target){
8+
const[rows,cols]=[matrix.length,matrix[0].length];
9+
let[left,right]=[0,((rows*cols)-1)];
3210

33-
returnfalse;
34-
}
35-
36-
//////////////////////////////////////////////////////////////////////////////
37-
// Double Binary Search
38-
// Time: O(log(mn)) Space: O(1)
39-
//////////////////////////////////////////////////////////////////////////////
11+
while(left<=right){
12+
constmid=(left+right)>>1;
13+
const[row,col]=[(Math.floor(mid/cols)),(mid%cols)]
14+
constguess=matrix[row][col];
4015

41-
/**
42-
*@param {number[][]} matrix
43-
*@param {number} target
44-
*@return {boolean}
45-
*/
46-
functionsearchMatrix(matrix,target){
47-
letrow=-1;
48-
leti=0;
49-
letj=matrix.length-1;
16+
constisTarget=guess===target;
17+
if(isTarget)returntrue;
5018

51-
while(i<=j){
52-
letm=Math.floor((i+j)/2);
53-
if(target<matrix[m][0]){
54-
j=m-1;
55-
}elseif(target===matrix[m][0]||target===top(matrix[m])){
56-
returntrue;
57-
}elseif(target<top(matrix[m])){
58-
row=m;
59-
break;
60-
}else{
61-
i=m+1;
62-
}
63-
}
19+
constisTargetGreater=guess<target;
20+
if(isTargetGreater)left=mid+1;
6421

65-
if(row<0){
66-
returnfalse;
22+
constisTargetLess=target<guess;
23+
if(isTargetLess)right=mid-1;
6724
}
6825

69-
constvals=matrix[row];
70-
i=1;
71-
j=vals.length-2;
72-
73-
while(i<=j){
74-
letm=Math.floor((i+j)/2);
75-
if(target<vals[m]){
76-
j=m-1;
77-
}elseif(target>vals[m]){
78-
i=m+1;
79-
}else{
80-
returntrue;
81-
}
82-
}
8326
returnfalse;
8427
}
85-
86-
/**
87-
*@param {!Array<*>} arr
88-
*@return {*}
89-
*/
90-
functiontop(arr){
91-
returnarr[arr.length-1];
92-
}

‎javascript/875-Koko-Eating-Bananas.js

Lines changed: 19 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -1,33 +1,30 @@
1-
//////////////////////////////////////////////////////////////////////////////
2-
// Binary Search Of Potential Answers
3-
// Time: O(n*log(m)) Space: O(1)
4-
//////////////////////////////////////////////////////////////////////////////
5-
61
/**
72
*@param {number[]} piles
83
*@param {number} h
4+
* Time O(N * log(M)) | Space O(1)
95
*@return {number}
106
*/
11-
functionminEatingSpeed(piles,h){
12-
letl=0;
13-
letr=Math.max.apply(Math,piles);
7+
varminEatingSpeed=function(piles,h){
8+
let[left,right]=[1,Math.max(...piles)];
9+
10+
while(left<right){
11+
constmid=(left+right)>>1;
12+
consthourSpent=getHourSpent(mid,piles);
13+
14+
constisTargetGreater=h<hourSpent;
15+
if(isTargetGreater)left=mid+1;
1416

15-
if(piles.length===h){
16-
returnr;
17+
constisTargetLess=hourSpent<=h;
18+
if(isTargetLess)right=mid;
1719
}
1820

19-
while(l<r){
20-
constm=Math.floor((l+r)/2);
21-
lethours=0;
22-
for(constpileofpiles){
23-
hours+=Math.ceil(pile/m);
24-
}
25-
if(hours>h){
26-
l=m+1;
27-
}else{
28-
r=m;
29-
}
21+
returnright;
22+
}
23+
24+
constgetHourSpent=(mid,piles,hourSpent=0)=>{
25+
for(constpileofpiles){
26+
hourSpent+=Math.ceil(pile/mid);
3027
}
3128

32-
returnl;
29+
returnhourSpent;
3330
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp