基础二分查找

标签：二分 right target nums 基础 middle 查找 区间 left

二分查找力扣题目链接

[704. 二分查找 - 力扣（LeetCode）]，

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

解题思路：

使用二分查找的方式来进行题解。确定给定的数组区间，确定middle。判断target与middle的关系，来选择target在区间的那部分。

　　if(target == nums[middle])

　　return middle;

else if(target < nums[middle])

//target 在区间左侧，变更右侧边界，由于nums[middle]与target不相等，且target在区间左侧，所以对比middle的前一个元素。最右侧边界即为middle -1;重新计算middle值，进行判断。

{right = middle -1;}

else if(target > nums[middle])

//target 在区间右侧，变更左侧边界，由于nums[middle]与target不相等，且target在区间左侧，所以对比middle的前一个元素。最右侧边界即为middle +1; 重新计算middle值，进行判断。

{left = middle+1;}

区间定义问题：

 

在二分查找中，常见的疑点就是区间的判断会很迷惑，不知道是选择左闭右开，还是选择左闭右闭区间。

情况一：

当使left <= right的时候，存在两种情况有效：left == right,left < right。

因此，数组的区间情况包括：

left = right, [left,right];

此时数组left = right时，对与数组元素的取值nums[right]是有效值，所以right值应为nums.size()-1;

这时数组的区间为左闭又闭。

情况二：

当时left<right的时候，仅有一种情况。

此时nums[right]为无效值。所以此时right的值为nums.size();

数组区间为左闭右开。

 

标签：二分,right,target,nums,基础,middle,查找,区间,left
From： https://www.cnblogs.com/kknothing/p/17124799.html