力扣：二分查找法和一些留意事项

题目描述：

解题

1. class Solution {
2.     public int search(int[] nums, int target) {
3.         int left = 0;
4.         int right = nums.length - 1;
5.         while(left <= right){
6.             int mid = (left + right) / 2;
7.             if(target > nums[mid]){
8.                 left = mid + 1;
9.             }else if(target < nums[mid]){
10.                 right = mid - 1;
11.             }else {
12.                 return mid;
13.             }
14.         }
15.         return -1;
16.     }
17. }

复制代码

问题：

在二分查找中，通常碰到的两个问题：

• while 循环的条件？
  a. left <= right ？
  b. left < right？
  
• right 每次移动的位置？
  a. right = mid - 1？
  b. right = mid？
  

以上两个问题的关键点就在于我们对于数组利用时，所选择的查询区间，一般分为两种：
3. 左闭右闭 ->> [ ] 表现从最左边到最右边的区间查找，例如[1, 3] 就是 1，2，3
4. 左闭右开 ->> [ ）表现从最左边到最右边 - 1的区间查找，例如[1,3)就是1，2
办理

以上两个问题的关键点就在于我们对于数组利用时，所选择的查询区间，一般分为两种：

• 左闭右闭 ->> [ ] 表现从最左边到最右边的区间查找，例如[1, 3] 就是 1，2，3
  
• 左闭右开 ->> [ ）表现从最左边到最右边 - 1的区间查找，例如[1,3)就是1，2
  

所以首先确定好自己所选取的区间就可以办理上述两个问题了：

• 左闭右闭，这分析我们需要查询的数据就是包罗在这个范围里面的，不在范围里面的都不满意条件查询，比如 [1,3]，就表现从1查到3。
  a. 这样第一个问题就可以办理了，我们可以举例子来分析，假如末了就剩了一个3，那么区间表现[3,3]符合我们上面的界说，在区间内的都需要查询。所以应该是 left <= right。
  b. 第二个问题也是同样的意思，当我们比较的是假如target < nums[mid]才需要对 right 赋值，那么这时着实已经对 mid 这个位置进行了比较，着实已经不满意我们的条件了，并不应该出如今我们的查询范围中，所以应该是 right = mid - 1，这样[left，right] 照旧满意左闭右闭，在整个区间内都进行查询。
  
• 左闭右开，这分析我们需要查询的数据着实是从左边开始到右边的数字 - 1的范围，并不包罗最右边的数字。比如[1,3)，就表现从 1 查到 2。
  a. 这样第一个问题就分析：当我们同样剩末了一个数字三的时候，区间表现[3,3)这并不符合我们区间的界说，既要查3，但是又不应该查3。所以我们应该是不能让left = right，所以应该是 left < right。
  b. 同样的第二个问题，这时候发现 mid 索引的位置着实已经不满意条件了，但是 mid - 1 的还没有查抄，所以我们需要包罗 mid - 1 的位置，这时我们就应该让 right = mid，这样也是符合我们的区间界说[left, right）但是不包罗right。
  

这样我们就办理了二分查找一些不确定的问题。
补充

假如选择左闭右开的区间去进行查询的话，那么 right 的起始位置应该是 num.length 而不是 num.length - 1。就是因为我们查询的时候并不包罗最右边的这个数字。
代码

左闭右闭

1. class Solution {
2.     public int search(int[] nums, int target) {
3.         int left = 0;
4.         int right = nums.length - 1;
5.         while(left <= right){
6.             int mid = (left + right) / 2;
7.             if(target > nums[mid]){
8.                 left = mid + 1;
9.             }else if(target < nums[mid]){
10.                 right = mid - 1;
11.             }else {
12.                 return mid;
13.             }
14.         }
15.         return -1;
16.     }
17. }

复制代码

左闭右开

1. class Solution {
2.     public int search(int[] nums, int target) {
3.         int left = 0;
4.         int right = nums.length;
5.         while(left < right){
6.             int mid = (left + right) / 2;
7.             if(target > nums[mid]){
8.                 left = mid + 1;
9.             }else if(target < nums[mid]){
10.                 right = mid;
11.             }else {
12.                 return mid;
13.             }
14.         }
15.         return -1;
16.     }
17. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。