题解 | #二分查找-II#

二分查找-II

http://www.nowcoder.com/practice/4f470d1d3b734f8aaf2afb014185b395

算法思想一：顺序遍历

解题思路：

对数组nums进行顺序遍历，因为数组是有序的，所以当遍历的元素与目标target相同时，即为第一个出现的target，返回该元素的索引即可

代码展示：

Python版本

class Solution:
    def search(self , nums , target ):
        # write code here
        # 顺序遍历
        for i in range(len(nums)):
            # 找到目标值返回目标值索引
            if nums[i] == target:
                return i
        # 没有找到返回
        return -1

复杂度分析

时间复杂度 $O(N)$ ： $N$ 表示数组的长度，最差情况下遍历数组时间为 $O(N)$

空间复杂度 $O(1)$ ：不需要额外空间

算法思想二：二分搜索

解题思路：

主要采用二分搜索法找到最小目标值索引

算法流程：

1、初始化low、high、mid三个初始变量， $mid = low+ (high- low) / 2$ ， $low = 0$ , $high= nums.length-1$

2、循环，循环停止条件 $low >= high$ ：

1、当 $nums[mid] > target$ ：所搜区间 $【low，mid-1】$

2、当 $nums[mid] < target$ ：所搜区间 $【mid+1，high】$

3、当 $nums[mid] == target$ ；需要向左遍历找到第一个出现的target

1、循环条件： $nums[mid-1] == nums[mid] and mid != 0$

2、 $mid = mid - 1$

4、跳出内层循环，返回 mid

图解：

代码展示：

JAVA版本

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
        // 初始化
        int low = 0;
        int high = nums.length-1;
        int mid = 0;
        // 循环跳出条件
        while(low <= high){
            mid = low+ (high- low) / 2;
            // 找到目标值
            if(nums[mid] == target){
                // 从当前索引向左遍历，找到最小索引的目标值
                while(mid != 0 &&(nums[mid-1] == nums[mid])){
                    mid--;
                }
                return mid;
            }
            // 二分缩小查找区间
            else if(nums[mid] > target){
                high = mid - 1;
            }
            else {
                low = mid + 1;
            }
        }
        return -1;
    }
}