First Position of Target

Easy For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity.

If the target number does not exist in the array, return -1.

Thoughts

最基本的bin search问题。用STL中lower_bound的实现方法找出数组中第一个和target相等或比target大的数(当target不在时)所在的index, 即最后start/end(它们俩最后相等)所在位置.

基于此思想把模板拓展成找第一个分界点(后半边第一个元素)所在位置. 当end == nums.len时分界点看成可以是非数组内元素, 否则是在nums里. 当落在分界点前时, 把对应的start/end移到mid并加一.

Code

    /**
     * @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) {
        int start = 0, end = nums.length - 1;
        // 防止陷入死循环
        while (start < end) {
            // 这么写是为了防止越界
            int mid = start + (end - start) / 2;
            if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }

        return end > 0 ? -1 : nums[end] == target ? start : -1;
    }

Analysis

Time Complexity: O(lgn)