牛客-NC105-二分查找-II

方法一：递归二分（自己写的）

思路：题目已经给出解题思路：二分查找，但这里需要注意限制条件：首次出现的位置，不可避免地，我们需要递归去二分查找target。当找到时，需要考虑在当前mid的左边可能还有更小的，所有我们需要再递归调用左边。

import java.util.*;


public class Solution {
   
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 如果目标值存在返回下标，否则返回 -1 * @param nums int整型一维数组 * @param target int整型 * @return int整型 */
    int ret = -1;
    public int search (int[] nums, int target) {
   
        // write code here
        helper(0, nums.length - 1, nums, target);
        return ret;
    }
    public void helper(int i, int j, int[] nums, int target) {
   
        int left = i;
        int right = j;
        if (left <= right) {
   
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
   
                helper(left, mid - 1, nums, target);
            } else if (nums[mid] < target) {
   
                helper(mid + 1, right, nums, target);
            } else {
   
                ret = ret == -1 ? mid : Math.min(ret, mid);
// System.out.println(left + "----" + right + "----" + mid);
                // 左边可能还有更小的
                helper(left, mid - 1, nums, target);
            }
        }
    }
}

时间复杂度： O(logN), 二分复杂度都是O(logN)。
空间复杂度： O(1), 未使用额外的空间(递归调用栈不知是否算额外空间)。

方法二：纯二分

思路：方法一是递归写法，其实使用while也能搞定，且更加简洁，应该算这道题的最优解了。

import java.util.*;


public class Solution {
   
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 如果目标值存在返回下标，否则返回 -1 * @param nums int整型一维数组 * @param target int整型 * @return int整型 */
    public int search (int[] nums, int target) {
   
        // write code here
        // for the last case
        if (nums.length == 0) return -1;
        int left = 0;
        int right = nums.length -1;
        while (left < right) {
   
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
   
                // 下一轮搜索的区间是 [left, mid - 1]
                right = mid - 1;
            } else if (nums[mid] == target) {
   
                // 下一轮搜索的区间是 [left, mid]
                right = mid;
            } else {
   
                // 下一轮搜索的区间是 [mid + 1, right]
                left = mid + 1;
            }
        }
        if (nums[left] == target) {
   
            return left;
        }
        return -1;
    }
}

时间复杂度： O(logN), 二分复杂度都是O(logN)。
空间复杂度： O(1), 未使用额外的空间。
总结：这题是朴素二分查找的变形，需要考虑第一次出现的位置，LeetCode上还有个更有挑战性的题目，详情请看link。