（LeetCode）Java 求解在排序数组中查找元素的第一个和最后一个位置

深碍√TFBOYSˉ_ 2022-10-25 04:47 47阅读 0赞

### 文章目录 ###

*   *  一、题目
     *  二、代码
     *  三、二分查找总结

## 一、题目 ##

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 \[-1, -1\]。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70]

--------------------

解析：  
该题利用二分查找：二分查找适合找一个顺序排列中符合条件的值，所以这里需要找两次

*  查找第一次出现的值
 *  查找第二次出现的值

## 二、代码 ##

class Solution { 
        public int[] searchRange(int[] nums, int target) { 
            if (nums.length == 0 || target > nums[nums.length - 1] || target < nums[0]) { 
                return new int[]{ -1, -1};
            }
            //二分查找适合查找一个符合条件的值，所以这里查找两次即可
            //查找第一次出现的值
            int start = firstTartet(nums, target);
            if (start == -1) { 
                return new int[]{ -1, -1};
            }
            int end = lastTarget(nums, target);
            return new int[]{ start, end};
        }
    
        public int firstTartet(int[] nums, int target) { 
            int left = 0;
            int right = nums.length - 1;
            while (left < right) { 
                //这里对应左半部：right = mid;
                int mid = left + (right - left) / 2;
                if (nums[mid] > target) { 
                    right = mid - 1;
                } else if (nums[mid] < target) { 
                    left = mid + 1;
                } else { 
                    //如果nums[mid]=target,那么首次出现的target一定在左半部
                    right = mid;
                }
            }
            return nums[left] != target ? -1 : left;
        }
    
        public int lastTarget(int[] nums, int target) { 
            int left = 0;
            int right = nums.length - 1;
            while (left < right) { 
                //这里对应右半部：left = mid;
                int mid = left + (right - left + 1) / 2;
                if (nums[mid] > target) { 
                    right = mid - 1;
                } else if (nums[mid] < target) { 
                    left = mid + 1;
                } else { 
                    //如果nums[mid]=target,那么最后一次出现的target一定在右半部
                    left = mid;
                }
            }
            //程序走到这里说明 nums 中一定存在 target，所以这里直接返回 left 即可。
            return left;
        }
    }

注意下数组的返回方式：`new int[] {-1,-1};`

## 三、二分查找总结 ##

左右边界向中间走，两边夹

1.  `while(left < right)` 这种写法表示在循环体内部排除元素；
2.  退出循环的时候 `left` 和 `right` 重合，区间 `[left, right]` 只剩下成 1 个元素，这个元素有可能 就是我们要找的元素。
3.  注意向上取整还是向下取整：

*  mid 如果被分到左半区间也就是 出现 right = mid 那么对应：`int mid = left + (right-left)/2;`

> 比如\[1,2,3,4\]，第一次mid=2

*  mid 如果被分到右半区间也就是 出现 left = mid 那么对应：`int mid = left + (right-left+1)/2;`

> 比如\[1,2,3,4\]，第一次mid=3

1.  退出循环时，根据题意看是否需要单独判断最后的那个数是不是目标元素

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70]: /images/20221024/8b07371fc38243c59f5d4e5a825006da.png