LeetCode704. 二分查找

题目卡片

题目链接：704. 二分查找 - 力扣（LeetCode）

类       型：数组

难       度：简单

目录

题目卡片

原题

Attention

Part1 影响初始边界的选择

Part2 影响循环判定条件

Part3 影响 middle的赋值情况

题解

1. 左闭右闭

2. 左闭右开

原题

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1。

你必须编写一个具有 O(log n) 时间复杂度的算法。
示例 1:

输入: nums= [-1,0,3,5,9,12], target = 9

输出: 4

解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2

输出: -1

解释: 2 不存在 nums 中因此返回 -1

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999, 9999]之间。

Attention

最重要的一步是选择有效区间，通常我们有两种选择方法：

1.  左闭右闭
2.  左闭右开

两者将会极大程度的影响算法的细节处理部分

Part1 影响初始边界的选择

 左闭右闭  [left, right]

Left = 0;Right = nums.length -1;

 左闭右开 [left, right)

Left = 0;Right = nums.length;

可以注意理解“有效区间”中的“有效”二字

Part2 影响循环判定条件

 左闭右闭  [left, right]

while(left <= right){...}

 左闭右开 [left, right)

while(left < right){...}

对于[left, right)这种情况，如果书写left <= right，就会出现异常，因为我们的right不是一个可以取到的有效数据，不应该用来直接衡量边界条件

Part3 影响 middle的赋值情况

 左闭右闭  [left, right]

if (nums[middle] > target) { right = middle - 1;} else if (nums[middle] < target) { left = middle + 1;} else if (nums[middle] == target) { return middle;}

 左闭右开 [left, right)

if (nums[middle] > target) { right = middle;} else if (nums[middle] < target) { left = middle + 1;} else if (nums[middle] == target) { return middle;}

nums[middle] > target是需要特殊讨论的！！！
因为这种情况是 left< target<middle<right；
我们要做的是 收紧右边界，但是基于两种有效区间定义的不用，给出了不一样的挪动方式：
 左闭右闭  [left, right] : right = middle - 1;
 左闭右开  [left, right) : right = middle;

但是注意，由于左边界一直是闭合的，所以 收缩左边界的代码段是不变的，一直是：
left = middle + 1;

题解

1. 左闭右闭

class Solution { public int search(int[] nums, int target) { // Step1. 确定左右边界 [left,right] int left = 0; // 因为右边为闭区间，所以right =num.length-1 int right = nums.length - 1; // Step2. 确定有效边界为[]，应该为<=，如果是<就会漏元素 while (left  target) { right = middle - 1; } else if (nums[middle] < target) { left = middle + 1; } else if (nums[middle] == target) { return middle; } } // Step4. 记住处理异常情况 return -1; }}

2. 左闭右开

class Solution { public int search(int[] nums, int target) { // Step1. 确定左右边界 [left,right) int left = 0; // 因为右边为开区间，所以right =num.length int right = nums.length; // Step2. 确定有效边界为[ )，应该为<，如果是<=就会讨论无效区域 while (left  target) { right = middle; } else if (nums[middle] < target) { left = middle + 1; } else if (nums[middle] == target) { return middle; } } // Step4. 记住处理异常情况 return -1; }}

声明

本文为技术总结沉淀，转载需注明原始出处链接，禁止任何形式的商业用途改编（如培训教材、付费教程等），技术讨论欢迎评论区留言，拒绝无意义抬杠。