leetcode 34. Search for a Range 二分查找

超、凢脫俗 2022-06-09 09:42 126阅读 0赞

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的上下index，使用遍历是可以的，但应该不是本题的考察要点，所以这里和上一题一样，使用了二分查找。

代码如下：

import java.util.Arrays;
    
    public class Solution
    {
        /*
         * 这是使用二分查找
         * */
        public int[] searchRange(int[] nums, int target)
        {
            int []res=new int[2];
            Arrays.fill(res, -1);
            if(nums==null || nums.length<=0)
                return res;
    
            if(nums.length==1 && nums[0]==target)
                    res[0]=res[1]=0;
            else
                binarySearch(nums,res,target,0,nums.length-1);
    
            return res;
        }
    
        public void binarySearch(int[] nums, int[] res, int target, int begin, int end) 
        {
            if(begin>end)
                return ;
            else if(begin==end)
            {
                //我这里是在找到target之后像前后面扩展，得到结果
                if(nums[begin]==target)
                {
                    int i=begin;
                    while(i>=0 && nums[i]==target)
                        i--;
                    res[0]=i+1;
    
                    i=begin;
                    while(i<nums.length && nums[i]==target)
                        i++;
                    res[1]=i-1;
                    return ;
                }else 
                    return ;
            }else 
            {
                int mid=(begin+end)/2;
                if(nums[mid]<target)
                    binarySearch(nums, res, target, mid+1, end);
                else 
                    binarySearch(nums, res, target, begin, mid);
            }
        }
    
        /*
         * 这个是通过遍历实现的
         * */
        public int[] searchRange11(int[] nums, int target)
        {
            int []res=new int[2];
            Arrays.fill(res, -1);
            if(nums==null || nums.length<=0)
                return res;
    
            if(nums.length==1 && nums[0]==target)
                res[0]=res[1]=0;
            else 
            {
                //超出范围的考虑
                int i=0,j=nums.length-1;
                if(target<nums[0] || target > nums[j])
                    return res;
    
                //我这里是遍历数组，其实使用二分查找或许更好
                while(i<j)
                {
                    if(target < nums[j])
                        j--;
                    if(nums[i] < target)
                        i++;
                    if(nums[i]==target && nums[j]==target)
                        break;
                }
    
                if(nums[i]==target && nums[j]==target)
                {
                    res[0]=i;
                    res[1]=j;
                }
            }
            return res;
        }
    }

下面是C++的做法，就是简单的二分查找，

代码如下：

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    class Solution 
    {
    public:
        vector<int> res;
        vector<int> searchRange(vector<int>& nums, int target) 
        {
            res.push_back(-1);
            res.push_back(-1);
            binarySearch(nums, target, 0, nums.size() - 1);
            return res;
        }
    
        void binarySearch(vector<int> nums, int target, int beg, int end)
        {
            if (beg > end)
                return;
            else if (beg == end)
            {
                if (nums[beg] == target)
                {
                    int i = beg;
                    while (i >= 0 && nums[i] == target)
                        i--;
                    res[0]=i + 1;
    
                    int j = beg;
                    while (j < nums.size() && nums[j] == target)
                        j++;
                    res[1] = j - 1;
                }
                else
                    return;
            }
            else
            {
                int mid = (end - beg) / 2 + beg;
                if (nums[mid] < target)
                    binarySearch(nums, target, mid + 1, end);
                else
                    binarySearch(nums, target, beg, mid);
            }
        }
    };

还有下面的非递归的二分查找

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    
    
    class Solution
    {
    public:
        vector<int> searchRange(vector<int>& a, int target)
        {
            vector<int> res(2, -1);
            int left = 0, right = a.size() - 1;
            while (left <= right)
            {
                int mid = (right - left) / 2 + left;
                if (a[mid] == target)
                {
                    int j = mid;
                    while(j >= 0 && a[j] == target)
                        j--;
                    res[0] = j + 1;
    
                    j = mid;
                    while (j < a.size() && a[j] == target)
                        j++;
                    res[1] = j - 1;
    
                    break;
                }
                else if (a[mid] > target)
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            return res;
        }
    };