We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
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 our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
二分查找细节是魔鬼。
取决于你的区间是闭区间[0,len-1],还是左闭右开 [0,len)
[0,len)分成[left,mid),[mid+1,right)
[0,len-1]分成[left,mid-1],[mid+1,right]
function binarySearch(nums: number[], target: number) { const Len = nums.length let left = 0, right = Len - 1 while (left <= right) { const mid = left + ((right - left) >> 1); if (nums[mid] == target) { return mid } else if (nums[mid] < target) { left = mid + 1 } else if (nums[mid] > target) { right = mid - 1 } } return -1 }
if (nums[mid] === target) right = mid - 1向左收缩
if (nums[mid] === target) right = mid - 1
function left_binarySearch(nums: number[], target: number) { const Len = nums.length let left = 0, right = Len - 1 while (left <= right) { const mid = left + ((right - left) >> 1); if (nums[mid] === target) { right = mid - 1 } else if (nums[mid] < target) { left = mid + 1 } else if (nums[mid] > target) { right = mid - 1 } } if (nums[left] !== target || left === Len) return -1 return left }
if (nums[mid] === target) left = mid + 1向右收缩
if (nums[mid] === target) left = mid + 1
function right_binarySearch(nums: number[], target: number) { const Len = nums.length let left = 0, right = Len - 1 while (left <= right) { const mid = left + ((right - left) >> 1); if (nums[mid] === target) { left = mid + 1 } else if (nums[mid] < target) { left = mid + 1 } else if (nums[mid] > target) { right = mid - 1 } } if (nums[right] !== target || right === Len) return -1 return right }
代码和思路都参考二分查找细节详解,顺便赋诗一首
The text was updated successfully, but these errors were encountered:
No branches or pull requests
二分查找
二分查找细节是魔鬼。
while (left <= right)与while (left < right)
取决于你的区间是闭区间[0,len-1],还是左闭右开 [0,len)
left = mid + 1,right = mid与left = mid + 1,right = mid - 1
[0,len)分成[left,mid),[mid+1,right)
[0,len-1]分成[left,mid-1],[mid+1,right]
在有序数组中查找目标元素
目标元素的左边界
if (nums[mid] === target) right = mid - 1
向左收缩目标元素的右边界
if (nums[mid] === target) left = mid + 1
向右收缩参考
代码和思路都参考二分查找细节详解,顺便赋诗一首
The text was updated successfully, but these errors were encountered: