(lintcode)第14题二分查找

要求：给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。

样例：在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3，返回2。

思路：使用递归，每次都找到中间那个数进行判断，直到区间第一个数的下标等于最后一个数的下标。判断的时候，对中间的数进行判断，分为3种情况，一种是刚好等于我们要找的数，这时候不能够直接返回下标，因为我们不确定这个数的前面是否存在着同样的数，所以，要对这个数前面的数进行查找，找到就返回前面的，没找到就返回中间数的下标

，当中间数小于目标数时，查找后一半，当中间数大于目标数的时候，查找前面一半。递归直到区间只有一个数。

代码如下：

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) {        //write your code here        return search(nums,target,0,nums.length);    }    public int search(int []nums,int target,int first,int last){        if(first==last){            if(nums[first]==target)                return first;            else return -1;        }else{            int avg=(first+last)/2;            if(nums[avg]==target){                if(search(nums,target,first,avg)==-1)//查找前一半有没有相同的数                    return nums[avg];                else                    return search(nums,target,first,avg);            }            else if(nums[avg]>target)                return search(nums,target,first,avg);            else if(nums[avg]<target){                return search(nums,target,avg+1,last);            }            return -1;        }    }}

如果有所帮助，脸皮厚求个赞~

此文章仅代表自己（本菜鸟）学习积累记录，或者学习笔记，如有侵权，请联系作者删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有错误之处，还望指出，感激不尽~

技术之路不在一时，山高水长，纵使缓慢，驰而不息。

公众号：秦怀杂货店

更多相关文章

随机推荐