java 范圍搜尋要怎么弄

Problem statement:

問(wèn)題陳述：

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

給定一個(gè)以升序排列的整數(shù)nums數(shù)組，請(qǐng)找到給定目標(biāo)值的開(kāi)始和結(jié)束位置。

Your algorithm's runtime complexity must be in order to less than O(n).

您的算法的運(yùn)行時(shí)復(fù)雜度必須小于O(n) 。

If the target is not found in the array, return [-1, -1].

如果在數(shù)組中找不到目標(biāo)，則返回[-1，-1] 。

Constraints:

限制條件：

1 <= t <= 100 1 <= n <= 1000000

Example:

例：

Test case 1: Input: arr = [5,6,7,8,8,10] target = 8Output: range is : [3, 4]Test case 2: Input: arr = [5,7,7,8,8,10] target = 6Output: range is: [-1,-1]

Explanation:

說(shuō)明：

Though the above solutions are self-explanatory, still for the first test case,For the first test case, Target is first present at index 3 and last one at 4. (0-based indexing)For the second test case, Target is not at all present and hence range is [-1,-1]

Solution approach

解決方法

It's quite similar to binary search. The modification is to not to stop when you get the target find. Search for the upper and lower elements to check if they are the same or not.

它與二進(jìn)制搜索非常相似。 修改是在找到目標(biāo)時(shí)不要停止。 搜索上部和下部元素以檢查它們是否相同。

Here goes the full algorithm,

這里是完整的算法，

Initialize the result range to be [-1,-1]

初始化結(jié)果范圍為[-1，-1]

If array size is 0

如果數(shù)組大小為0

return

返回

result;

結(jié)果 ;

Initialize left = 0, right = n-1;

初始化left = 0，right = n-1;

while(left<=right)mid=(left+right)/2;if(nums[mid]==target) //once found search for rangeset i=mid;set j=mid;while(i>=left && nums[i]==target)Decrease i;while(j<=right && nums[j]==target)Increase j;Result is [i+1,j-1] else if(nums[mid]<target)left=mid+1;elseright=mid-1;end if End while

Result stores the starting and ending point of range. If target is not found then the range will be the initial one, [-1,-1]

結(jié)果存儲(chǔ)范圍的起點(diǎn)和終點(diǎn)。 如果找不到目標(biāo)，則范圍將是初始范圍[-1，-1]

Let's solve with the first test case,left = 0 right = 5 mid = 2 a[mid]<target, left = mid+1 = 3a[mid] == target so traverse left and right from this range found to be [3,4]For the second test case, It simple comes out of the loop

C++ Implementation:

C ++實(shí)現(xiàn)：

#include <bits/stdc++.h> using namespace std;vector<int> searchRange(vector<int>& nums, int target) {int n = nums.size();vector<int> p(2, -1);if (n == 0)return p;int left = 0, right = n - 1;int mid;while (left <= right) {mid = (left + right) / 2;if (nums[mid] == target) { //once found search for rangeint i = mid;int j = mid;while (i >= left && nums[i] == target)i--;while (j <= right && nums[j] == target)j++;p[0] = i + 1;p[1] = j - 1;return p;}else if (nums[mid] < target)left = mid + 1;elseright = mid - 1;}return p; }int main() {int t;cout << "Enter number of testcases\n";cin >> t;while (t--) {int n;cout << "Enter length of array\n";cin >> n;cout << "Enter the sorted vector\n";vector<int> arr(n);for (int i = 0; i < n; i++)cin >> arr[i];int k;cout << "Enter target no\n";cin >> k;vector<int> result = searchRange(arr, n);cout << "range is: [" << result[0] << "," << result[1] << "]\n";}return 0; }

Output:

輸出：

Enter number of testcases 2 Enter length of array 6 Enter the sorted vector 5 6 7 8 8 10 Enter target no 8 range is: [3,4] Enter length of array 6 Enter the sorted vector 5 7 7 8 8 10 Enter target no 6 range is: [-1,-1]

翻譯自: https://www.includehelp.com/icp/search-for-a-range.aspx

java 范圍搜尋要怎么弄

總結(jié)

以上是生活随笔為你收集整理的java 范围搜寻要怎么弄_搜索范围的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。