Skip to content

Commit b131fee

Browse files
BarklimBarklim
Barklim
authored and
Barklim
committed
binary search
1 parent 590e0e2 commit b131fee

File tree

7 files changed

+214
-2
lines changed

7 files changed

+214
-2
lines changed

‎0033-search-in-rotated-sorted-array.js‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -42,3 +42,40 @@ var search = function(nums, target) {
4242

4343
return -1;
4444
};
45+
46+
// var search = function(nums, target) {
47+
// let l = 0;
48+
// let r = nums.length - 1;
49+
50+
// while (l < r) {
51+
// const m = Math.floor((l + r) / 2);
52+
// if (nums[m] > nums[r]) {
53+
// l = m + 1;
54+
// } else {
55+
// r = m;
56+
// }
57+
// }
58+
59+
// const pivot = l;
60+
61+
// const result = binarySearch(nums, target, 0, pivot - 1);
62+
// if (result !== -1) {
63+
// return result;
64+
// }
65+
66+
// return binarySearch(nums, target, pivot, nums.length - 1);
67+
// };
68+
69+
// var binarySearch = function(nums, target, left, right) {
70+
// while (left <= right) {
71+
// const mid = Math.floor((left + right) / 2);
72+
// if (nums[mid] === target) {
73+
// return mid;
74+
// } else if (nums[mid] < target) {
75+
// left = mid + 1;
76+
// } else {
77+
// right = mid - 1;
78+
// }
79+
// }
80+
// return -1;
81+
// }

‎0153-find-minimum-in-rotated-sorted-array.js‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -37,3 +37,26 @@ var findMin = function(nums) {
3737

3838
return nums[left];
3939
};
40+
41+
// var findMin = function(nums) {
42+
// let l = 0;
43+
// let r = nums.length - 1;
44+
// let res = nums[0];
45+
46+
// while (l <= r) {
47+
// if (nums[l] <= nums[r]) {
48+
// res = Math.min(res, nums[l]);
49+
// break;
50+
// }
51+
52+
// // let m = l + Math.floor((r - l) / 2);
53+
// let m = Math.floor((l + r) / 2);
54+
// res = Math.min(res, nums[m]);
55+
// if (nums[m] >= nums[l]) {
56+
// l = m + 1;
57+
// } else {
58+
// r = m - 1;
59+
// }
60+
// }
61+
// return res;
62+
// };

‎example/4.BinarySearch/0004.js‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
/**
2+
* @param {number[]} nums1
3+
* @param {number[]} nums2
4+
* @return {number}
5+
*/
6+
var findMedianSortedArrays = function(nums1, nums2) {
7+
8+
};
9+
10+
const example1 = search([1,3], [2]); // 2
11+
const example2 = search([1,2], [3,4]); // 2.5
12+
const example3 = search([1,2], [3]); // 2
13+
const example4 = search([1,3], [2,4]); // 2.5
14+
15+
console.log(example1);
16+
console.log(example2);
17+
console.log(example3);
18+
console.log(example4);

‎example/4.BinarySearch/0033.js‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
/**
2+
* @param {number[]} nums
3+
* @param {number} target
4+
* @return {number}
5+
*/
6+
var search = function(nums, target) {
7+
8+
};
9+
10+
const example1 = search([4,5,6,7,0,1,2], 0); // 4
11+
const example2 = search([4,5,6,7,0,1,2], 3); // -1
12+
const example3 = search([1], 0); // -1
13+
const example4 = search([3,4,5,1,2], 1); // 3
14+
const example5 = search([4,5,6,7,0,1,2], 2); // 6
15+
const example6 = search([11,13,15,17], 13); // 1
16+
const example7 = search([4,5,0,1,2,3], 0); // 2
17+
const example8 = search([4,5,6,7], 5); // 1
18+
19+
console.log(example1);
20+
console.log(example2);
21+
console.log(example3);
22+
console.log(example4);
23+
console.log(example5);
24+
console.log(example6);
25+
console.log(example7);
26+
console.log(example8);

‎example/4.BinarySearch/0153.js‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
/**
2+
* @param {number[]} nums
3+
* @return {number}
4+
*/
5+
var findMin = function(nums) {
6+
7+
};
8+
9+
const example1 = findMin([3,4,5,1,2]); // 1
10+
const example2 = findMin([4,5,6,7,0,1,2]); // 0
11+
const example3 = findMin([11,13,15,17]); // 11
12+
const example4 = findMin([4,5,0,1,2,3]); // 0
13+
const example5 = findMin([4,5,6,7]); // 4
14+
15+
console.log(example1);
16+
console.log(example2);
17+
console.log(example3);
18+
console.log(example4);
19+
console.log(example5);

‎example/4.BinarySearch/0981.js‎

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
var TimeMap = function() {
2+
3+
};
4+
5+
/**
6+
* @param {string} key
7+
* @param {string} value
8+
* @param {number} timestamp
9+
* @return {void}
10+
*/
11+
TimeMap.prototype.set = function(key, value, timestamp) {
12+
13+
};
14+
15+
/**
16+
* @param {string} key
17+
* @param {number} timestamp
18+
* @return {string}
19+
*/
20+
TimeMap.prototype.get = function(key, timestamp) {
21+
22+
};
23+
24+
/**
25+
* Your TimeMap object will be instantiated and called as such:
26+
* var obj = new TimeMap()
27+
* obj.set(key,value,timestamp)
28+
* var param_2 = obj.get(key,timestamp)
29+
*/
30+
31+
// Input
32+
// ["TimeMap", "set", "get", "get", "set", "get", "get"]
33+
// [[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
34+
// Output
35+
// [null, null, "bar", "bar", null, "bar2", "bar2"]
36+
37+
38+
const timeMap = new TimeMap();
39+
timeMap.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1.
40+
timeMap.get("foo", 1); // return "bar"
41+
timeMap.get("foo", 3); // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar".
42+
timeMap.set("foo", "bar2", 4); // store the key "foo" and value "bar2" along with timestamp = 4.
43+
timeMap.get("foo", 4); // return "bar2"
44+
timeMap.get("foo", 5); // return "bar2"
45+
46+
// var TimeMap = function() {
47+
// this.keyStore = new Map();
48+
// };
49+
50+
// /**
51+
// * @param {string} key
52+
// * @param {string} value
53+
// * @param {number} timestamp
54+
// * @return {void}
55+
// */
56+
// TimeMap.prototype.set = function(key, value, timestamp) {
57+
// if (!this.keyStore.has(key)) {
58+
// this.keyStore.set(key, []);
59+
// }
60+
// this.keyStore.get(key).push([timestamp, value]);
61+
// };
62+
63+
// /**
64+
// * @param {string} key
65+
// * @param {number} timestamp
66+
// * @return {string}
67+
// */
68+
// TimeMap.prototype.get = function(key, timestamp) {
69+
// const values = this.keyStore.get(key) || [];
70+
// let left = 0;
71+
// let right = values.length - 1;
72+
// let result = '';
73+
74+
// while (left <= right) {
75+
// const mid = Math.floor((left + right) / 2);
76+
// if (values[mid][0] <= timestamp) {
77+
// result = values[mid][1];
78+
// left = mid + 1;
79+
// } else {
80+
// right = mid - 1;
81+
// }
82+
// }
83+
84+
// return result;
85+
// };

‎example/README.md‎

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -70,8 +70,12 @@ Better order to solve problems
7070
### [Binary Search](https://github.com/Barklim/leetcode-javascript/tree/master/example/4.BinarySearch)
7171

7272
704. Binary Search
73-
74. Search a 2D Matrix
74-
875. Koko Eating Bananas
73+
- 74. Search a 2D Matrix
74+
- 875. Koko Eating Bananas
75+
- 153. Find Minimum in Rotated Sorted Array
76+
- 33. Search in Rotated Sorted Array
77+
- 981. Time Based Key-Value Store
78+
- 4. Median of Two Sorted Arrays
7579

7680
### HashMap
7781

0 commit comments

Comments
 (0)