Formed in 2009, the Archive Team (not to be confused with the archive.org Archive-It Team) is a rogue archivist collective dedicated to saving copies of rapidly dying or deleted websites for the sake of history and digital heritage. The group is 100% composed of volunteers and interested parties, and has expanded into a large amount of related projects for saving online and digital history.
第 150 题：二分查找如何定位左边界和右边界 #320
Open
Labels
Comments
二分查找基础代码//递归查找
function erfen_digui(arr, val, left = 0, right = arr.length - 1) {
if (left > right) {
return -1;
}
let cent = Math.floor((right + left) / 2);
if (arr[cent] === val) {
return `最终查找结果下标为${cent}`;
} else if (arr[cent] > val) {
right = cent - 1;
} else {
left = cent + 1;
}
return erfen_digui(arr, val, left, right);
}
//非递归查找
function erfen_feidigui(arr, val) {
let left = 0,
right = arr.length - 1;
while (left <= right) {
let cent = left + Math.floor((right - left) / 2);
if (arr[cent] === val) {
return `最终查找结果下标为${cent}`;
} else if (arr[cent] > val) {
right = cent - 1;
} else {
left = cent + 1;
}
}
return -1;
}
//左边界查找（查找第一个元素）
function erfen_digui(arr, val, left = 0, right = arr.length - 1) {
if (left > right) {
return -1;
}
let cent = Math.floor((right + left) / 2);
if (arr[cent] === val) {
/****************改动点********************/
if (arr[cent - 1] === val) {
right = cent - 1;
} else {
return `最终查找结果下标为${cent}`;
}
/*****************************************/
} else if (arr[cent] > val) {
right = cent - 1;
} else {
left = cent + 1;
}
return erfen_digui(arr, val, left, right);
}
// 二分查找右边界（查找最后一个元素）
function erfen_digui(arr, val, left = 0, right = arr.length - 1) {
if (left > right) {
return -1;
}
let cent = Math.floor((right + left) / 2);
if (arr[cent] === val) {
/****************改动点********************/
if (arr[cent + 1] === val) {
left = cent + 1;
} else {
return `最终查找结果下标为${cent}`;
}
/*****************************************/
} else if (arr[cent] > val) {
right = cent - 1;
} else {
left = cent + 1;
}
return erfen_digui(arr, val, left, right);
} |
function search(arr, target) {
let begin = 0;
let end = arr.length - 1;
const result = [];
while (begin <= end) {
const mid = (begin + end) >>> 1;
if (target === arr[mid]) {
let left = mid;
let right = mid;
result.push(mid)
while (--left && left > 0) {
if (arr[mid] === arr[left]) {
result.unshift(left)
}
}
while (++right && right < arr.length) {
if (arr[mid] === arr[right]) {
result.push(right)
}
}
break;
} else if (target > arr[mid]) {
begin = mid + 1;
} else {
end = mid - 1;
}
}
return result
}
// 返回出现目标数据的索引位置数组 第一次出现位置为result[0] 最后一次为 result[result.length -1]
//const list1 = [1, 4, 4, 4, 5, 6, 7];
//console.log(search(list1, 4)); [1, 2, 3] 第一次出现索引位置为1 最后一次出现的索引位置为3 |
|
function twoY(arr,str){ |
题目介绍二分查找定位左边界和右边界 knuth 说过，二分查找虽然思路很简单，但是细节是魔鬼。 通常，我会根据$[left, right]$ 和 $[left,right)$ 来分类各种不同的写法。
function binarySearch(arr, target) {
let left = 0;
let right = arr.length;
while (left < right) {
let mid = first + Math.floor((right-left)/2);
if(arr[mid] < target) left = mid + 1
else right = mid
}
return left;
}
function binarySearch(arr, target) {
let left = 0;
let right = arr.length;
while (left < right) {
let mid = first + Math.floor((right-left)/2);
if(arr[mid] < target) left = mid + 1
else right = mid
}
return left < arr.length && arr[left] === target;
}
function binarySearch(arr, target) {
let left = 0;
let right = arr.length;
while (left < right) {
let mid = first + Math.floor((right-left)/2);
if(arr[mid] < target) left = mid + 1
else right = mid
}
return left-1;
} |
/**
* 寻找目标值左侧边界
* @param {*} nums
* @param {*} target
*/
function findLeft(nums, target) {
let left = 0;
let right = nums.length;
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (nums[mid] === target) {
right = mid; //关键地方
} else if (nums[mid] > target) {
right = mid; //关键地方
} else {
left = mid + 1;
}
}
return left;
}
/**
* 寻找目标值右侧边界
* @param {*} nums
* @param {*} target
*/
function findRight(nums, target) {
let left = 0;
let right = nums.length;
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (nums[mid] === target) {
left = mid + 1 //关键地方
} else if (nums[mid] > target) {
right = mid;
} else {
left = mid + 1;//关键地方
}
}
return left;
}
let arr = [1, 3, 4, 4, 6, 8, 10];
console.log('left bound:', findLeft(arr, 4))
console.log('right bound:', findRight(arr, 4)) |
|
|
递归实现 /**
* @param {Array} arr 数组
* @param {Number} item 待查找项
* @param {Number} min 第一个索引
* @param {Number} max 最后一个索引
*/
function _binarySearch(arr, item, min = 0, max = arr.length - 1) {
const half = Math.floor(min + (max - min) / 2)
if (item < arr[half]) return _binarySearch(arr, item, min, half - 1)
if (item > arr[half]) return _binarySearch(arr, item, half + 1, max)
return half
}
/**
* @param {Array} arr 数组
* @param {Number} item 待查找项
*/
const binarySearch = (arr, item) => _binarySearch(arr, item) // 隐藏多余参数循环实现： /**
* @param {Array} arr 数组
* @param {Number} item 待查找项
*/
function binarySearch(arr, item) {
let min = 0
let max = arr.length - 1
let half
while (min <= max) {
half = Math.floor(min + (max - min) / 2)
if (item > arr[half]) {
min = half + 1
} else if (item < arr[half]) {
max = half - 1
} else {
break
}
}
return half
}测试： /**
* test
*/
const res = binarySearch([1, 3, 66, 88, 233, 666], 666)
console.log('res: ', res) // 5 |
// 非递归解法, 查lastIndex原理一样
function searchFirstIndex(arr, target) {
let firstIndex = -1
let leftIndex = 0
let rightIndex = arr.length // 初始区间为[0, arr.length)
// leftIndex == rightIndex时终止循环
while(leftIndex < rightIndex) {
let midIndex = Math.floor((leftIndex + rightIndex) / 2)
let mid = arr[midIndex]
if(mid == target) {
if(firstIndex == -1 || firstIndex > midIndex) {
firstIndex = midIndex
rightIndex = midIndex // 继续向左查找
}
} else if(mid < target) {
leftIndex = midIndex + 1
} else if(mid > target) {
rightIndex = midIndex
}
}
return firstIndex
} |
findRight 应当返回left - 1 |
function findLeft(nums: number[], target: number): number {
let left = 0
let right = nums.length
while (left < right) {
const mid = left + Math.floor((right - left) / 2)
if (nums[mid] === target) {
right = mid
} else if (nums[mid] < target) {
left = mid + 1
} else {
right = mid
}
}
if (nums[left] !== target) {
return -1
}
return left
}
function findRight(nums: number[], target: number): number {
let left = 0
let right = nums.length
while (left < right) {
const mid = left + Math.floor((right - left) / 2)
if (nums[mid] === target) {
left = mid + 1
} else if (nums[mid] < target) {
left = mid + 1
} else {
right = mid
}
}
if (nums[left - 1] !== target) {
return -1
}
return left - 1
} |
|
稍微对二分查找改造一下就可以，找到目标值之后左右滑动确定值 function findBoundary(source, target, start = 0, end = source.length - 1) {
if (end - start === 1) {
if (source[start] !== target) return -1;
return leftAndRight(source, target, start);
}
const mid = start + Math.floor((end - start) / 2);
if (source[mid] < target) {
return findBoundary(source, target, mid, end);
} else if (source[mid] > target) {
return findBoundary(source, target, start, mid);
} else {
return leftAndRight(source, target, mid);
}
}
function leftAndRight(source, target, mid) {
let i = mid;
let j = mid;
while (source[i - 1] === target) {
i--;
}
while (source[j + 1] === target) {
j++;
}
return [i, j];
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
不使用JS数组API，查找有序数列最先出现的位置和最后出现的位置
The text was updated successfully, but these errors were encountered: