首页 > 代码库 > 【leetcode】Search for a Range

【leetcode】Search for a Range

2024-07-13 06:33:38   219人阅读

Given a sorted array of integers, 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].

 

题解：按照题目要求的时间复杂度，使用二分方法，设置私有两个变量begin和end，记录最终找到的range的范围，在递归二分的过程中，如果找到了目标，根据此时target在数组中的下表不断的缩小begin和扩大end，这样最终begin和end就是最大的range范围了。

主要步骤如下：

  1. 如果A[mid] == target，根据mid的值更新begin和end值。然后判断左边数组最右边的元素是否仍然和target相等，如果相等要继续二分搜索左边的数组；右边的数组也要做同样的处理；
  2. 如果A[mid] < target，递归搜索右边的数组；
  3. 如果A[mid] > target,递归搜索左边的数组；

数组[2,2,2,2]的搜索过程如下：

所以最终返回的range是[0,2]。

代码如下：

 1 public class Solution { 2     private int begin; 3     private int end; 4     public void BinarySearch(int[] A,int target,int s,int e){ 5         if(s > e) 6             return; 7         int mid = s + (e - s)/2; 8         if(target == A[mid]){ 9             if(mid < begin)10                 begin = mid;11             if(mid > end)12                 end = mid;13             if(mid - 1>=0 && A[mid-1] == target)14                 BinarySearch(A, target, s, mid-1);15             if(mid + 1 < A.length && A[mid+1] == target)16                 BinarySearch(A, target, mid+1, e);17         }18         else{19             if(A[mid] > target)20                 BinarySearch(A, target, s, mid-1);21             else {22                 BinarySearch(A, target, mid+1, e);23             }24         }25     }26     public int[] searchRange(int[] A, int target) {27         begin = A.length;28         end = -1;29         BinarySearch(A, target, 0, A.length-1);30         31         int[] answer = new int[2];32         if(begin == A.length && end == -1){33             answer[0] = answer[1] = -1;34         }35         else{36             answer[0] = begin;37             answer[1] = end;38         }39         return answer;40     }41 }


联系
我们