力扣：二分查找法和一些留意事项
题目描述：https://i-blog.csdnimg.cn/direct/20f8f24f515e489abb9e4496db79c34f.png解题
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = (left + right) / 2;
if(target > nums){
left = mid + 1;
}else if(target < nums){
right = mid - 1;
}else {
return mid;
}
}
return -1;
}
}
问题：
在二分查找中，通常碰到的两个问题：
[*]while 循环的条件？
a. left <= right ？
b. left < right？
[*]right 每次移动的位置？
a. right = mid - 1？
b. right = mid？
以上两个问题的关键点就在于我们对于数组利用时，所选择的查询区间，一般分为两种：
3. 左闭右闭 ->> [ ] 表现从最左边到最右边的区间查找，例如 就是 1，2，3
4. 左闭右开 ->> [ ）表现从最左边到最右边 - 1的区间查找，例如[1,3)就是1，2
办理
以上两个问题的关键点就在于我们对于数组利用时，所选择的查询区间，一般分为两种：
[*]左闭右闭 ->> [ ] 表现从最左边到最右边的区间查找，例如 就是 1，2，3
[*]左闭右开 ->> [ ）表现从最左边到最右边 - 1的区间查找，例如[1,3)就是1，2
所以首先确定好自己所选取的区间就可以办理上述两个问题了：
[*]左闭右闭，这分析我们需要查询的数据就是包罗在这个范围里面的，不在范围里面的都不满意条件查询，比如 ，就表现从1查到3。
a. 这样第一个问题就可以办理了，我们可以举例子来分析，假如末了就剩了一个3，那么区间表现符合我们上面的界说，在区间内的都需要查询。所以应该是 left <= right。
b. 第二个问题也是同样的意思，当我们比较的是假如target < nums才需要对 right 赋值，那么这时着实已经对 mid 这个位置进行了比较，着实已经不满意我们的条件了，并不应该出如今我们的查询范围中，所以应该是 right = mid - 1，这样 照旧满意左闭右闭，在整个区间内都进行查询。
[*]左闭右开，这分析我们需要查询的数据着实是从左边开始到右边的数字 - 1的范围，并不包罗最右边的数字。比如[1,3)，就表现从 1 查到 2。
a. 这样第一个问题就分析：当我们同样剩末了一个数字三的时候，区间表现left < right。
b. 同样的第二个问题，这时候发现 mid 索引的位置着实已经不满意条件了，但是 mid - 1 的还没有查抄，所以我们需要包罗 mid - 1 的位置，这时我们就应该让 right = mid，这样也是符合我们的区间界说。
这样我们就办理了二分查找一些不确定的问题。
补充
假如选择左闭右开的区间去进行查询的话，那么 right 的起始位置应该是 num.length 而不是 num.length - 1。就是因为我们查询的时候并不包罗最右边的这个数字。
代码
左闭右闭
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = (left + right) / 2;
if(target > nums){
left = mid + 1;
}else if(target < nums){
right = mid - 1;
}else {
return mid;
}
}
return -1;
}
}
左闭右开
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length;
while(left < right){
int mid = (left + right) / 2;
if(target > nums){
left = mid + 1;
}else if(target < nums){
right = mid;
}else {
return mid;
}
}
return -1;
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]