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

refactor: js - binary search#464

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Merged
mitchellirvin merged 2 commits intoneetcode-gh:mainfromaakhtar3:bsearch
Jul 30, 2022
Merged
Show file tree
Hide file tree
Changes fromall commits
Commits
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
30 changes: 19 additions & 11 deletionsjavascript/153-Find-Minimum-in-Rotated-Sorted-Array.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -1,17 +1,25 @@
/**
* @param {number[]} nums
* Time O(log(N)) | Space O(1)
* @return {number}
*/
var findMin = function (nums) {
let left = 0;
let right = nums.length - 1;
while (right > left) {
let mid = Math.floor((right + left) / 2);
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
var findMin = function(nums) {
let [ left, right ] = [ 0, (nums.length - 1) ];

while (left < right) {
const mid = (left + right) >> 1;
const guess = nums[mid];
const [ leftNum, rightNum ] = [ nums[left], nums[right] ];

const isTarget = leftNum < rightNum;
if (isTarget) return leftNum;

const isTargetGreater = leftNum <= guess;
if (isTargetGreater) left = mid + 1;

const isTargetLess = guess < leftNum;
if (isTargetLess) right = mid;
}

return nums[left];
};
};
55 changes: 29 additions & 26 deletionsjavascript/33-Search-in-Rotated-Sorted-Array.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -1,39 +1,42 @@
/**
* @param {number[]} nums
* @param {number} target
* Time O(log(N)) | Space O(1)
* @return {number}
*/
var search = function (nums, target) {
let left = 0;
let right = nums.length - 1;

var search = (nums, target) => {
let [ left, right ] = [ 0, nums.length - 1 ];

while (left <= right) {
let mid = Math.floor((left + right) / 2);
const mid = (left + right) >> 1;
const guess = nums[mid];
const [ leftNum, rightNum ] = [ nums[left], nums[right] ];

if (nums[mid] === target) {
return mid;
}
const isTarget = guess === target;
if (isTarget) return mid;

const isAscending = leftNum <= guess;
if (isAscending) {
const isInRange = leftNum <= target;
const isLess = target < guess;

// Checking if the left side is sorted
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target <= nums[mid]) {
// thus target is in the left
right = mid - 1;
} else {
// thus target is in the right
left = mid + 1;
}
const isTargetGreater = !(isInRange && isLess);
if (isTargetGreater) left = mid + 1;

const isTargetLess = isInRange && isLess;
if (isTargetLess) right = mid - 1;
}

// Otherwise, the right side is sorted
else {
if (nums[mid] <= target && target <= nums[right]) {
// thus target is in the right
left = mid + 1;
} else {
// thus target is in the left
right = mid - 1;
}
const isDescending = guess < leftNum;
if (isDescending) {
const isGreater = guess < target;
const isInRange = target <= rightNum;

const isTargetGreater = isGreater && isInRange;
if (isTargetGreater) left = mid + 1;

const isTargetLess = !(isGreater && isInRange);
if (isTargetLess) right = mid - 1;
}
}

Expand Down
64 changes: 39 additions & 25 deletionsjavascript/4-Median-Of-Two-Sorted-Arrays.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -1,34 +1,48 @@
/**
* @param {number[]} nums1
* @param {number[]} nums2
* Time O(log(N * M)) | Space O(N)
* @return {number}
*/
var findMedianSortedArrays = function (nums1, nums2) {
let [A, B] = [nums1, nums2];
const total = nums1.length + nums2.length;
const half = Math.floor(total / 2);
var findMedianSortedArrays = function(nums1, nums2) {
const canSwap = nums2.length < nums1.length;
if (canSwap) [nums1, nums2] = [nums2, nums1];

if (B.length < A.length) {
[A, B] = [B, A];
}
let [ left, right ] = [ 0, nums1.length - 1 ];
const totalLength = nums1.length + nums2.length
const mid = totalLength >> 1;
const isEven = (totalLength % 2) === 0;

let [l, r] = [0, A.length - 1];
while (true) {
const i = l + r;
const j = half - i - 2;

const Aleft = i >= 0 ? A[i] : -Infinity;
const Aright = i + 1 < A.length ? A[i + 1] : Infinity;
const Bleft = j >= 0 ? B[j] : -Infinity;
const Bright = j + 1 < B.length ? B[j + 1] : Infinity;

if (Aleft <= Bright && Bleft <= Aright) {
if (total % 2) {
return Math.min(Aright, Bright);
}

return (Math.max(Aleft, Bleft) + Math.min(Aright, Bright)) / 2;
} else if (Aleft > Bright) r = i - 1;
else l = i + 1;
const mid1 = left + right;
const mid2 = (mid - mid1) - 2;
const { aLeft, aRight, bLeft, bRight } = getPointers(nums1, mid1, nums2, mid2);

const isTarget = (aLeft <= bRight) && (bLeft <= aRight);
if (isTarget) return isEven
? (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2
: Math.min(aRight, bRight);

const isTargetGreater = aLeft <= bRight;
if (isTargetGreater) left = mid1 + 1;

const isTargetLess = bRight < aLeft;
if (isTargetLess) right = mid1 - 1;
}
};
}

const getPointers = (nums1, mid1, nums2, mid2) => {
const getLeft = (nums, index) => 0 <= index
? nums[index]
: -Infinity;

const [ aLeft, bLeft ] = [ getLeft(nums1, mid1), getLeft(nums2, mid2) ];

const getRight = (nums, index) => (index + 1) < nums.length
? nums[index + 1]
: Infinity;

const [ aRight, bRight ] = [ getRight(nums1, mid1), getRight(nums2, mid2) ];

return { aLeft, aRight, bLeft, bRight };
}
27 changes: 13 additions & 14 deletionsjavascript/704-Binary-Search.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -1,26 +1,25 @@
/**
* @param {number[]} nums
* @param {number} target
* Time O(log(N)) | Space O(1)
* @return {number}
*/
var search = function (nums, target) {
let left = 0;
let right = nums.length - 1;
var search = function(nums, target) {
let [ left, right ] = [ 0, (nums.length - 1) ];

while (left <= right) {
let middle = Math.floor((left + right) / 2);
const mid = (left + right) >> 1;
const guess = nums[mid];

if (nums[middle] === target) {
return middle;
} else if (nums[middle] < target) {
left = middle + 1;
} else {
right = middle - 1;
}
const isTarget = guess === target;
if (isTarget) return mid;

const isTargetGreater = guess < target;
if (isTargetGreater) left = mid + 1;

const isTargetLess = target < guess;
if (isTargetLess) right = mid - 1;
}

return -1;
};

// Runtime: 98 ms, faster than 34.02% of JavaScript online submissions for Binary Search.
// Memory Usage: 44.3 MB, less than 99.18% of JavaScript online submissions for Binary Search.
93 changes: 14 additions & 79 deletionsjavascript/74-Search-A-2D-Matrix.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -1,92 +1,27 @@
//////////////////////////////////////////////////////////////////////////////
// Single Binary Search
// Time: O(log(mn)) Space: O(1)
//////////////////////////////////////////////////////////////////////////////

/**
* @param {number[][]} matrix
* @param {number} target
* Time O(log(ROWS * COLS)) | Space O(1)
* @return {boolean}
*/
function searchMatrix(matrix, target) {
const width = matrix[0].length;
const height = matrix.length;
let i = 0;
let j = height * width - 1;

while (i <= j) {
const m = Math.floor((i + j) / 2);
const r = Math.floor(m / width);
const c = m % width;

if (matrix[r][c] === target) {
return true;
}

if (matrix[r][c] < target) {
i = m + 1;
} else {
j = m - 1;
}
}
var searchMatrix = function(matrix, target) {
const [ rows, cols ] = [ matrix.length, matrix[0].length ];
let [ left, right ] = [ 0, ((rows * cols) - 1) ];

return false;
}

//////////////////////////////////////////////////////////////////////////////
// Double Binary Search
// Time: O(log(mn)) Space: O(1)
//////////////////////////////////////////////////////////////////////////////
while (left <= right) {
const mid = (left + right) >> 1;
const [ row, col ] = [ (Math.floor(mid / cols)), (mid % cols) ]
const guess = matrix[row][col];

/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
function searchMatrix(matrix, target) {
let row = -1;
let i = 0;
let j = matrix.length - 1;
const isTarget = guess === target;
if (isTarget) return true;

while (i <= j) {
let m = Math.floor((i + j) / 2);
if (target < matrix[m][0]) {
j = m - 1;
} else if (target === matrix[m][0] || target === top(matrix[m])) {
return true;
} else if (target < top(matrix[m])) {
row = m;
break;
} else {
i = m + 1;
}
}
const isTargetGreater = guess < target;
if (isTargetGreater) left = mid + 1;

if (row < 0) {
return false;
const isTargetLess = target < guess;
if (isTargetLess) right = mid - 1;
}

const vals = matrix[row];
i = 1;
j = vals.length - 2;

while (i <= j) {
let m = Math.floor((i + j) / 2);
if (target < vals[m]) {
j = m - 1;
} else if (target > vals[m]) {
i = m + 1;
} else {
return true;
}
}
return false;
}

/**
* @param {!Array<*>} arr
* @return {*}
*/
function top(arr) {
return arr[arr.length - 1];
}
41 changes: 19 additions & 22 deletionsjavascript/875-Koko-Eating-Bananas.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -1,33 +1,30 @@
//////////////////////////////////////////////////////////////////////////////
// Binary Search Of Potential Answers
// Time: O(n*log(m)) Space: O(1)
//////////////////////////////////////////////////////////////////////////////

/**
* @param {number[]} piles
* @param {number} h
* Time O(N * log(M)) | Space O(1)
* @return {number}
*/
function minEatingSpeed(piles, h) {
let l = 0;
let r = Math.max.apply(Math, piles);
var minEatingSpeed = function(piles, h) {
let [ left, right ] = [ 1, Math.max(...piles) ];

while (left < right) {
const mid = (left + right) >> 1;
const hourSpent = getHourSpent(mid, piles);

const isTargetGreater = h < hourSpent;
if (isTargetGreater) left = mid + 1;

if (piles.length === h) {
return r;
const isTargetLess = hourSpent <= h;
if (isTargetLess) right = mid;
}

while (l < r) {
const m = Math.floor((l + r) / 2);
let hours = 0;
for (const pile of piles) {
hours += Math.ceil(pile / m);
}
if (hours > h) {
l = m + 1;
} else {
r = m;
}
return right;
}

const getHourSpent = (mid, piles, hourSpent = 0) => {
for (const pile of piles) {
hourSpent += Math.ceil(pile / mid);
}

returnl;
returnhourSpent;
}
Loading
[8]ページ先頭
©2009-2025 Movatter.jp