二分查找（左闭右闭区间）
思路
利用 二分思想
复杂度
-
时间复杂度：
O(logn)，其中 n 是数组的长度 -
空间复杂度：
O(1)
代码实现
function search(nums: number[], target: number): number {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
// 求出 mid 的索引（向下取整）
let mid = (left + right) >>> 1;
if (nums[mid] == target) {
// 由于是搜索一个数字，而不是一个范围，找到后直接停止循环，返回结果
return mid;
} else if (nums[mid] < target) {
// 当 target 大于 中间数，说明 target 在中间数的右侧，则收缩左边界
// +1 是为了将中间数刨除去
left = mid + 1;
} else if (nums[mid] > target) {
// 当 target 小于 中间数，说明 target 在中间数的左侧，则收缩右边界
// -1 是为了将中间数刨除去
right = mid - 1;
}
}
return -1;
};
二分查找（左闭右开区间）
思路
利用 二分思想
复杂度
-
时间复杂度：
O(logn)，其中 n 是数组的长度； -
空间复杂度：
O(1)；
代码实现
function search(nums: number[], target: number): number {
let left = 0;
let right = nums.length;
while (left < right) {
// 求出 mid 的索引（向下取整）
let mid = (left + right) >>> 1;
if (nums[mid] == target) {
// 由于是搜索一个数字，而不是一个范围，找到后直接停止循环，返回结果
return mid;
} else if (nums[mid] < target) {
// 当 target 大于 中间数，说明 target 在中间数的右侧，则收缩左边界
// +1 是为了将中间数刨除去
left = mid + 1;
} else if (nums[mid] > target) {
// 当 target 小于 中间数，说明 target 在中间数的左侧，则收缩右边界
// -1 是为了将中间数刨除去
right = mid;
}
}
return -1;
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
114.二叉树展开为链表
上一篇
评论
