[704] Binary search
Category | Difficulty | Likes | Dislikes |
---|---|---|---|
algorithms | Easy (56.01%). | 280 | – |
Given an ordered (ascending) integer array of n elements, nums, and a target value, write a function that searches for the target in NUMs, returning a subindex if the target value exists, or -1 otherwise.
Individual solution
var search = function (nums, target) {
if(! nums.includes(target)) {return -1;
}
if (nums[0] === target) {
return 0;
}
if (nums[1] === target) {
return 1;
}
let mid = parseInt(nums.length / 2)
if (nums[mid] < target) {
for (let i = mid + 1; i < nums.length; i++) {
if (target === nums[i]) returni; }}else {
for (let j = 0; j < mid; j++) {
if (target === nums[j]) returnj; }}}Copy the code
Accepted
- 46/46 cases passed (84 ms)
- Your runtime beats 58.95% of javascript submissions
- Your memory usage in the linked list (10000 MB)
Analysis of the
In the previous idea, mid was fixed, didn’t participate in the loop, and actually only implemented the dichotomy once. Therefore, the left and right endpoints L and r of the array subscript are defined, and mid is determined by finding the average value of L and r. Mid can change with the change of L and r.
To optimize the
let l = 0, r = nums.length;
while (l <= r) {
let mid = parseInt((l + r) / 2);
if (nums[mid] === target) {
return mid;
} else {
if (r - l === 1) {
return -1; // If only one number is left but it is not equal to target
}
else if (nums[mid] < target) {
l = mid + 1; // New loop range will discard mid, because nums[mid] has been determined not to equal target (otherwise return mid)
}
else if(nums[mid] > target) { r = mid; }}}}Copy the code
Accepted
- 46/46 cases passed (76 ms)
- Your runtime beats 79.62 % of javascript submissions
- Your memory usage in the linked list (0.0001KB)
[278] The first incorrect version
Category | Difficulty | Likes | Dislikes |
---|---|---|---|
algorithms | Easy (45.31%). | 362 | – |
You are a product manager and are currently leading a team to develop a new product. Unfortunately, the latest version of your product does not pass the quality test. Since each version is based on the previous version, all versions after the wrong version are wrong.
Suppose you have N versions [1, 2… n] and you want to find the first incorrect version that causes all subsequent versions to fail.
You can determine if the version number is wrong in the unit test by calling the bool isBadVersion(Version) interface. Implement a function to find the first incorrect version. You should try to minimize the number of calls to the API.
Personal solution (error)
var solution = function (isBadVersion) {
/ * * *@param {integer} n Total versions
* @return {integer} The first bad version
*/
return function (n) {
// let arr = [];
// for (let i = 0; i <= n; i++) {
// arr.push(i);
// }
// let l = 0, r = arr.length; Delete. You can use dichotomy without building an array.
let l = 1, r = n;
while (l < r) {
let mid = parseInt((l + r) / 2);
/ / delete. The target value is found by approximating the answer interval to 1.
// if (isBadVersion(arr[mid]) === false && isBadVersion(arr[mid + 1]) === true) return mid + 1;
if (isBadVersion(mid)) { // If the conditional is itself a Boolean.
r = mid;
} else
// else if (isBadVersion(arr[mid]) === false) {
l = mid + 1;
// } else {
// r = mid;
// }
}
return l;
};
};
Copy the code
Accepted
- 22/22 cases passed (56 ms)
- Your runtime beats 99.43% of javascript submissions
- Your memory usage in the linked list (0.0001KB)
Analysis of the
The key point is that when L =r, the interval length of the target value is 1, that is, the target value is found. And when l
If you write binary search in question [704] the same way:
[704] Optimization
var search = function (nums, target) {
let l = 0, r = nums.length;
while (l < r) {
let mid = parseInt((l + r) / 2);
if (nums[mid] < target) {
l = mid + 1;
}
else{ r = mid; }}if(nums[l] ! == target)return -1;
else return l;
}
Copy the code
Accepted
- 46/46 cases passed (72 ms)
- Your runtime beats 88.84% of javascript submissions
- Your memory Usage in the linked list (10000 MB)
【35】
[35] Search insertion position
Category | Difficulty | Likes | Dislikes |
---|---|---|---|
algorithms | Easy (46.96%). | 977 | – |
Given a sort array and a target value, find the target value in the array and return its index. If the target value does not exist in the array, return the order in which it will be inserted.
You must use order log n algorithms.
Individual solution
var searchInsert = function(nums, target) {
const n = nums.length;
let left = 0, right = n - 1, ans = n;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (target <= nums[mid]) {
ans = mid;
right = mid;
} else {
left = mid + 1; }}return ans;
};
Copy the code
Accepted
- 62/62 cases passed (96 ms)
- Your runtime beats 14.67% of javascript submissions
- Your memory Usage in the linked list (35.6MB)
To optimize the
var searchInsert = function (nums, target) {
let l = 0, r = nums.length;
while (l < r) {
let mid = parseInt((l + r) / 2);
if (nums[mid] < target) {
l = mid + 1;
} else{ r = mid; }}if (nums[l] < target) return l + 1;
else return l;
};
Copy the code
Accepted
- 62/62 cases passed (76 ms)
- Your runtime beats 75.02 % of javascript submissions
- Your memory Usage in the linked list (10000 MB)