【D19】二分查找&在排序数组中查找元素的第一个和最后一个位置&

今日主题，二分查找。

• 计算mid的时候需要防止溢出，当left和right太大时，mid = ( left + right ) / 2有可能会移除，因此，最好使用mid = left + ( right - left ) / 2。

704. 二分查找

问题描述

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

解题思路

采用两端都闭合的搜索区间[left，right]实现。

代码实现

class Solution {
    public int search(int[] nums, int target) {
        int index = -1;
        int left = 0, right = nums.length - 1;
        while(left <= right){
            int mid = left + (right -left) / 2;
            if(nums[mid] > target){
                //target在mid左侧,搜索区间变为[left, mid - 1]
                right = mid - 1;
            }else if(nums[mid] < target){
                //target在mid右侧,搜索区间变为[mid + 1, right]
                left = mid + 1;
            }else{
                //找到了target, 结束循环
                index = mid;
                break;
            }
        }
        return index;
    }
}

34. 在排序数组中查找元素的第一个和最后一个位置

问题描述

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。

解题思路

用两次二分查找，分别找到target在数组中的左右边界即可。

代码实现

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int len = nums.length;
        int[] res = new int[] {-1, -1};
        if(len > 0){
            res[0] = getLeftBound(nums,target);
            res[1] = getRightBound(nums, target);
        }
        return res;
    }

    //(1)找出给定目标值在数组中的开始位置，目标值不存在则返回-1
    public int getLeftBound(int[] nums, int target){
        int left = 0, right = nums.length - 1;
        while(left <= right){
            int mid = left + (right -left) / 2;
            if(nums[mid] > target){
                //target在mid左侧,搜索区间变为[left, mid - 1]
                right = mid - 1;
            }else if(nums[mid] < target){
                //target在mid右侧,搜索区间变为[mid + 1, right]
                left = mid + 1;
            }else{
                //nums[mid] == target不返回，继续向左搜索左边界
                right = mid - 1;   
            }
        }
        //循环结束时，left = right + 1。
        if(left >= nums.length || nums[left] != target){
            //如果所有元素都小于target，则left会越界
            return -1;
        }
        return  left;
    }

    //(2)找出给定目标值在数组中的结束位置，目标值不存在则返回-1
    public int getRightBound(int[] nums, int target){
        int left = 0, right = nums.length - 1;
        while(left <= right){
            int mid = left + (right -left) / 2;
            if(nums[mid] > target){
                //target在mid左侧,搜索区间变为[left, mid - 1]
                right = mid - 1;
            }else if(nums[mid] < target){
                //target在mid右侧,搜索区间变为[mid + 1, right]
                left = mid + 1;
            }else{
                //nums[mid] == target不返回，继续向右搜索右边界
                left = mid + 1;   
            }
        }
        //循环结束时，right = left - 1。
        if(right < 0  || nums[right] != target){
            //如果所有元素都大于target，则right会越界
            return -1;
        }
        return  right;
    } 
}

33. 搜索旋转排序数组

问题描述

整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的索引，否则返回 -1 。
你能设计一个时间复杂度为 O(log n) 的解决方案吗？

解题思路

这道题考查的是二分查找。

代码实现

class Solution {
    public int search(int[] nums, int target) {
       int left = 0, right = nums.length -1,index = -1;
    
       while(left <= right){
           int mid = left + (right - left) / 2;
           if(nums[mid] == target){
               index = mid;
               break;
           }
           //mid的左、右两个区间一定至少有一个是升序排列的
           if(nums[mid] >= nums[left]){
                //左侧升序
                if(nums[mid] > target && nums[left] <= target){
                    //并且target在此范围内，则搜索区间一定在左侧
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }  
           }else{
               if(nums[mid] < target && nums[right] >= target){
                   left = mid + 1;
               }else{
                   right = mid -1;
               }
           }
       }
       return index;
    }
}