LeetCode Binary Search All In One
Binary Search
二分查找算法
https://leetcode-cn.com/problems/binary-search/
https://leetcode-cn.com/problems/binary-search/solution/er-fen-cha-zhao-by-leetcode/
复杂度分析
时间复杂度：mathcal{O}(log N)O(logN)。
空间复杂度：mathcal{O}(1)O(1)。
LeetCode Binary Search Best Solutions in JavaScript
- 位运算
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
const search = (nums, target) => {
if(nums.length === 0){
return -1;
}
let lo = 0;
let hi = nums.length - 1;
while(lo <= hi){
// 位运算 12 >> 1 === 6 ✅
const mid = lo + ((hi - lo) >> 1);
if(nums[mid] === target){
return mid;
}else if(nums[mid] < target){
lo = mid + 1;
}else{
hi = mid - 1;
}
}
return -1;
};
- 经典双指针
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function(nums, target) {
let left = 0;
let right = nums.length-1
let middle
while(right >= left){
middle = Math.floor((left+right)/2)
const midval = nums[middle]
if(midval === target) return middle;
else if(midval > target) right = middle-1;
else left = middle +1;
}
return -1
};
bad
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function(nums, target) {
const findValue = (arr, target) => {
let result = -1;
let len = arr.length;
let index = Math.floor(len / 2);
let mid = arr[index];
let leftArr = arr.slice(0, index)
let rightArr = arr.slice(index + 1, len)
if(mid === target) {
result = nums.indexOf(mid);
} else {
if(mid > target) {
// left
result = findValue(leftArr, target)
}
if(mid < target) {
// right
result = findValue(rightArr, target)
}
}
return result;
}
return findValue(nums, target);
};
refs
https://leetcode.com/problemset/all/
https://leetcode-cn.com/problemset/all/
©xgqfrms 2012-2020
www.cnblogs.com 发布文章使用：只允许注册用户才可以访问！