题目

描述

• 请实现有重复数字的升序数组的二分查找
  给定一个 元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的第一个出现的target，如果目标值存在返回下标，否则返回 -1。

方法一

思路

在有重复数字的升序数组中找一个下标最小的target，且题目要求就是使用二分查找，所以方法必然是二分查找了，只需要处理重复数字就可以了，那么很容想到，在找到target后，再往左遍历，找到target最小的下标。

具体步骤

• 1.求mid；
• 2.比较nums[mid]与target值；
• 3.不同，返回1；
• 4.相同，从当前点，往左遍历，直至与target值不同时，返回加一的下标。
• 代码如下：

  import java.util.*;
  public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 如果目标值存在返回下标，否则返回 -1
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {
        // 数组为空直接返回
        if (nums == null || nums.length == 0){
            return -1;
        }
        int right = nums.length - 1;
        int left = 0;
        int mid = 0;
        // 二分查找
        while (left <= right){
            mid = left + (right - left)/2;
            if (nums[mid] < target){
                left = mid + 1;
            }else if(nums[mid] > target)
            {
                right = mid - 1;
            }else{
                // 找到target，往左找第一次出现的下标
                while(mid != 0 && nums[mid] == nums[mid-1]){
                    --mid;
                }
                return mid;
            }
        }
        return -1;
    }
  }

• 时间复杂度：，二分查找。
• 空间复杂度：，常数级空间复杂度。

  方法二

  思路

• 方法一在找到target值后还需要往左遍历，其实是可以省去的，可以直接通过二分查找往左逼近。如：当nums[mid]<target时，左指针left直接置为mid+1，慢慢逼近target。

  具体步骤

• 参考下图的栗子：
  
• 代码如下：

  import java.util.*;
  public class Solution {
  /**
  * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
  *
  * 如果目标值存在返回下标，否则返回 -1
  * @param nums int整型一维数组 
  * @param target int整型 
  * @return int整型
  */
  public int search (int[] nums, int target) {
     // 数组为空直接返回
     if (nums == null || nums.length == 0){
         return -1;
     }
     int right = nums.length - 1;
     int left = 0;
     int mid = 0;
     // 往左逼近
     while (left < right){
         mid = left + (right - left) / 2;
         // target在mid右边
         if (nums[mid] < target){
             left = mid + 1;
         }else{
             right = mid;
         }
     }
     // 返回第一次出现的下标
     return nums[left] == target ? left : -1;
  }
  }

• 时间复杂度：，二分查找。
• 空间复杂度：，常数级空间复杂度。