[leetcode-二分查找]--34. Search for a Range

刺骨的言语ヽ痛彻心扉 2022-07-12 02:58 93阅读 0赞

Question 34. Search for a Range

> Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.
> 
> Your algorithm’s runtime complexity must be in the order of O(log n).
> 
> If the target is not found in the array, return \[-1, -1\].
> 
> For example,  
> Given \[5, 7, 7, 8, 8, 10\] and target value 8,  
> return \[3, 4\].
> 
> 中文：有一个整型升序序列，序列里面可能存在重复值，找到给定值target的起始位置和结束位置。
> 
> 规定时间复杂度是 O（logn）

根据题目的时间复杂度的要求，很容易的就可以得出此题用二分查找是最合适的。先用二分查找找到target的位置，然后从target的索引开始分别往前往后查找，找到边界。

实现源码：

private static int[] result = new int[2];
    
    /** * 非递归方式查找 * @param nums * @param target * @return 查找到的索引值 */
    public static int[] binarySearch1(int[] nums, int target){
        int lo=0, hi=nums.length-1;
    
        int mid;//中间索引
    
        int[] re = new int[2];
    
        while (lo <= hi){
            mid = (lo+hi)/2;
    
            if(nums[mid] == target){
                //然后再当前mid的前后找
                int low , high;
                low = high = mid;
                while (low >=0 && nums[low] == nums[mid]){
                    low--;
                }
                while (high <=nums.length-1 && nums[high] == nums[mid]){
                    high++;
                }
                re[0] = low+1;
                re[1] = high-1;
                return re;
            } else if(nums[mid] < target){
                lo = mid+1;
            }else{
                hi = mid-1;
            }
        }
        re[0] = -1;
        re[1] = -1;
        return re;
    }

以上是以非递归方式实现的，递归方式基本一样。

本文完整源码github地址：  
[https://github.com/leetcode-hust/leetcode/blob/master/louyuting/src/leetcode/Question34.java][https_github.com_leetcode-hust_leetcode_blob_master_louyuting_src_leetcode_Question34.java]

[https_github.com_leetcode-hust_leetcode_blob_master_louyuting_src_leetcode_Question34.java]: https://github.com/leetcode-hust/leetcode/blob/master/louyuting/src/leetcode/Question34.java