Range of numbers
Given an array of integers of length n in ascending order, and q queries.
For each query, the start and end positions of an element k are returned (positions counted from 0).
If the element does not exist in the array, return-1 -1。
Input format
The first line contains integers n and q, representing the length of the array and the number of questions.
The second line contains n integers (all in the range of 1∼100001∼10000), representing the complete array.
Next, the q line, each line contains an integer k, representing a query element.
Output format
There are q rows in total, each row contains two integers, representing the starting position and ending position of the desired element.
If the element does not exist in the array, return-1 -1。
Data range
1≤n≤1000001≤q≤100001≤k≤10000
Enter a sample:
6 3
1 2 2 3 3 4
3
4
5
Output sample:
3 4
5 5
-1 -1
Points to note
- During the search process, the interrupt conditions are:
lowi <= highi - In the binary process, if the conditions are not met, the conditions need to be reduced by half (excluding the original boundary)
- . :
lowi = mid + 1,highi = mid - 1
- . :
nums_len, query = map(int, input().split())
nums = list(map(int, input().split()))
start, end = 0, nums_len - 1
def find_index(i):
lowi = start
highi = nums_len - 1
while low <= highi:
# print("test")
mid = (lowi + highhi) // 2
if nums[mid] < i:
lowi = mid + 1
elif nums[mid] > i:
highi = mid - 1
elif nums[mid] == i:
left = mid
right = mid
while left > 0 and nums[left - 1] == nums[mid]:
left -= 1
while right < nums_len - 1 and nums[right + 1] == nums[mid]:
right += 1
return [left, right]
else:
result = [-1, -1]
return result
for i in range(query):
# Use binary
query_k = int(input())
result = find_index(query_k)
print(str(result[0]) + ' ' + str(result[1]))