二分查找首次出现

题目

在一个升序数组中查找特定值首次出现的位置,若无则返回-1,http://www.lintcode.com/zh-cn/problem/first-position-of-target/

分析

这是一个二分查找问题,但多了一个规则,就是要找出目标值首次出现的位置,考虑到数组内部可能出现多个相同值的元素,因此需要在二分查找的代码上做一点点小改进即可,改动很简单,直接在代码中注释说明。

代码


    int search(int[] nums, int target, int start, int end){
        // 二分查找时只剩两个元素的情况
        if(end == start+1){
            if(nums[start] == target) return start;
            if(nums[end] == target) return end;
            return -1;
        }
        // 计算二分坐标
        int mid = (end + start)>>1 ;
        if(nums[mid] == target){
        // 若找到目标元素,还需查看前者是否存在等值元素
            while( mid>0 && (nums[mid-1] == target) ){
                mid--;
            }
            return mid;
        } // 继续二分查找
        else if(nums[mid] > target) return search(nums, target, start, mid);
        else return search(nums, target, mid+1, end);
    }
    /**
     * @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 < 1) return -1;
        return search(nums, target, 0, nums.length-1);
    }
Show Comments

Get the latest posts delivered right to your inbox.