LintCode 14. First Position of Target 原创Java参考解答

问题描述

http://www.lintcode.com/en/problem/first-position-of-target/

解题思路

1. 先检查数组nums是否为null或者为空数组，若是则直接返回-1。
2. 用二分法在数组中查找target值的位置。若查到了，不直接返回该target位置，而是继续以该位置开始的前面部分继续进行二分查找。以此来查找target在数组中第一次出现的位置。

参考代码

class Solution { 
    /** 
     * @param nums: The integer array. 
     * @param target: Target to find. 
     * @return: The first position of target. Position starts from 0. 
     */ 
    public int binarySearch(int[] nums, int target) { 
        if (nums == null || nums.length == 0) { 
            return -1; 
        } 
         
        int start = 0; 
        int end = nums.length - 1; 
         
        while (start + 1 < end) { 
            int mid = start + (end - start) / 2; 
            if (nums[mid] == target) { 
                end = mid; 
            } else if (nums[mid] > target) { 
                end = mid; 
            } else { 
                start = mid; 
            } 
        } 
         
        if (nums[start] == target) { 
            return start; 
        } else if (nums[end] == target) { 
            return end; 
        } 
         
        return -1; 
    } 
}

相关题目

LintCode All in One 原创题目讲解汇总