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

Commit597b1d0

Browse files
committed
refactor: js - binary search
1 parent2615e7b commit597b1d0

7 files changed

+195
-238
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(logN) | 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+
};
Lines changed: 37 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -1,44 +1,44 @@
11
/**
22
*@param {number[]} nums
33
*@param {number} target
4+
* Time O(logN) | Space O(1)
45
*@return {number}
56
*/
6-
varsearch=function(nums,target){
7-
letleft=0;
8-
letright=nums.length-1;
7+
varsearch=(nums,target)=>{
8+
let[left,right]=[0,nums.length-1];
99

10-
while(left<=right){
11-
letmid=Math.floor((left+right)/2);
12-
13-
if(nums[mid]===target){
14-
returnmid;
15-
}
16-
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-
23-
}else{
24-
// thus target is in the right
25-
left=mid+1;
26-
}
27-
}
28-
29-
// Otherwise, the right side is sorted
30-
else{
31-
if(nums[mid]<=target&&target<=nums[right]){
32-
// thus target is in the right
33-
left=mid+1;
34-
35-
}else{
36-
// thus target is in the left
37-
right=mid-1;
38-
}
10+
while(left<=right){
11+
constmid=(left+right)>>1;
12+
constguess=nums[mid];
13+
const[leftNum,rightNum]=[nums[left],nums[right]];
14+
15+
constisTarget=guess===target;
16+
if(isTarget)returnmid;
17+
18+
constisAscending=leftNum<=guess;
19+
if(isAscending){
20+
constisInRange=leftNum<=target;
21+
constisLess=target<guess;
22+
23+
constisTargetGreater=!(isInRange&&isLess);
24+
if(isTargetGreater)left=mid+1;
25+
26+
constisTargetLess=isInRange&&isLess;
27+
if(isTargetLess)right=mid-1;
28+
}
29+
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;
40+
}
3941
}
40-
41-
}
42-
43-
return-1;
44-
};
42+
43+
return-1;
44+
};
Lines changed: 40 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -1,36 +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)
10-
11-
if(B.length<A.length){
12-
[A,B]=[B,A]
13-
}
14-
15-
let[l,r]=[0,A.length-1]
7+
varfindMedianSortedArrays=function(nums1,nums2){
8+
constcanSwap=nums2.length<nums1.length;
9+
if(canSwap)[nums1,nums2]=[nums2,nums1];
10+
11+
let[left,right]=[0,nums1.length-1];
12+
consttotalLength=nums1.length+nums2.length
13+
constmid=totalLength>>1;
14+
constisEven=(totalLength%2)===0;
15+
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-
}
32-
elseif(Aleft>Bright)r=i-1
33-
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;
3431
}
35-
};
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)];
3646

47+
return{ aLeft, aRight, bLeft, bRight};
48+
}

‎javascript/704-Binary-Search.js

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

1110
while(left<=right){
12-
letmiddle=Math.floor((left+right)/2);
11+
constmid=(left+right)>>1;
12+
constguess=nums[mid];
13+
14+
constisTarget=guess===target;
15+
if(isTarget)returnmid;
1316

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

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

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

Lines changed: 17 additions & 84 deletions
Original file line numberDiff line numberDiff line change
@@ -1,94 +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-
13-
constwidth=matrix[0].length;
14-
constheight=matrix.length;
15-
leti=0;
16-
letj=height*width-1;
17-
18-
while(i<=j){
19-
constm=Math.floor((i+j)/2);
20-
constr=Math.floor(m/width);
21-
constc=m%width;
22-
23-
if(matrix[r][c]===target){
24-
returntrue;
25-
}
26-
27-
if(matrix[r][c]<target){
28-
i=m+1;
29-
}else{
30-
j=m-1;
31-
}
32-
}
33-
34-
returnfalse;
35-
}
7+
varsearchMatrix=function(matrix,target){
8+
const[rows,cols]=[matrix.length,matrix[0].length];
9+
let[left,right]=[0,((rows*cols)-1)];
3610

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

42-
/**
43-
*@param {number[][]} matrix
44-
*@param {number} target
45-
*@return {boolean}
46-
*/
47-
functionsearchMatrix(matrix,target){
48-
49-
letrow=-1;
50-
leti=0;
51-
letj=matrix.length-1;
52-
53-
while(i<=j){
54-
letm=Math.floor((i+j)/2);
55-
if(target<matrix[m][0]){
56-
j=m-1;
57-
}elseif(target===matrix[m][0]||target===top(matrix[m])){
58-
returntrue;
59-
}elseif(target<top(matrix[m])){
60-
row=m;
61-
break;
62-
}else{
63-
i=m+1;
64-
}
65-
}
66-
67-
if(row<0){
68-
returnfalse;
69-
}
70-
71-
constvals=matrix[row];
72-
i=1;
73-
j=vals.length-2;
74-
75-
while(i<=j){
76-
letm=Math.floor((i+j)/2);
77-
if(target<vals[m]){
78-
j=m-1;
79-
}elseif(target>vals[m]){
80-
i=m+1;
81-
}else{
82-
returntrue;
83-
}
16+
constisTarget=guess===target;
17+
if(isTarget)returntrue;
18+
19+
constisTargetGreater=guess<target;
20+
if(isTargetGreater)left=mid+1;
21+
22+
constisTargetLess=target<guess;
23+
if(isTargetLess)right=mid-1;
8424
}
85-
returnfalse;
86-
}
8725

88-
/**
89-
*@param {!Array<*>} arr
90-
*@return {*}
91-
*/
92-
functiontop(arr){
93-
returnarr[arr.length-1];
26+
returnfalse;
9427
}

0 commit comments

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