Python – Element Index in Range Tuples

Sometimes, while working with Python data, we can have a problem in which we need to find the element position in continuous equi ranged tuples in list. This problem has applications in many domains including day-day programming and competitive programming. Let’s discuss certain ways in which this task can be performed.
 

Input : 
test_list = [(0, 10), (11, 20), (21, 30), (31, 40)] 
K = 37 
Output : 3
Input : 
test_list = [(0, 9), (10, 19), (20, 29), (30, 39)] 
K = 37 
Output : 3 
 

Method #1 : Using loop 
This is brute force way in which this task can be performed. In this, we iterate for all the elements in the list and then using comparison operators, find the position of the desired element.
 

The original list is : [(0, 10), (11, 20), (21, 30), (31, 40), (41, 50)]
The position of element : 3

 
Method #2 : Using formula 
The element position can also be divided without using a loop, but to extract the same using division of element with the range size, being it consistent.

The original list is : [(0, 10), (11, 20), (21, 30), (31, 40), (41, 50)]
The position of element : 3

Method #3 : Using binary search to find the tuple containing the element.

Approach

This code implements a binary search algorithm to find the index of the tuple in the list test_list that contains the element K within its range. The binary_search function takes in the list test_list and the element K. It initializes two pointers, start and end, to the first and last indices of the list, respectively. It then repeatedly computes the midpoint of the range (mid), and checks if K falls within the range of the tuple at that index. If it does, it returns the index mid. If K is less than the minimum value in the range of the tuple at mid, it searches the left half of the list by updating end to mid – 1. If K is greater than the maximum value in the range of the tuple at mid, it searches the right half of the list by updating start to mid + 1. The function returns -1 if K is not found in any tuple.The element_index_range_tuples function simply calls the binary_search function with the given inputs test_list and K, and returns the result.

Algorithm

1. Define a binary search function to find the tuple containing the element.
2. Initialize ‘start’ to 0 and ‘end’ to the length of the list minus 1.
3. Calculate the mid-point using (start + end) // 2.
4. Check if the element lies within the range of the tuple at the mid-point using an if condition.
5. If it does, return the index of the tuple.
6. Otherwise, check if the element is less than the starting value of the tuple at the mid-point.
7. If it is, set ‘end’ to mid-point minus 1.
8. Otherwise, set ‘start’ to mid-point plus 1.
9. Repeat steps 3 to 8 until the element is found or the list is exhausted.
10. Return -1 if the element is not found.

3

Time Complexity: O(log n), where n is the length of the list.
Auxiliary Space: O(1)

Method #4 :Using numpy:

1. Convert the list of tuples to a NumPy array using np.array(test_list).
2. Use NumPy’s where function with the condition (arr[:, 0] <= K) & (arr[:, 1] > K) to get the indices of the ranges that contain the element K. This returns an array of indices that satisfy the condition.
3. Get the first index from the array of indices using [0], since there should only be one range that contains the element K
4. Get the range at the index using test_list[idx] to get the range tuple that contains the element K.

Output:

The original list is : [(0, 10), (11, 20), (21, 30), (31, 40), (41, 50)]
The position of element:  3

The time complexity: O(1), which means it has a constant time complexity. This is because the code uses a simple formula to calculate the index of the range that contains a given element K, without looping through the list or performing any significant operations

The space complexity :O(1) as well, because it only uses a few variables to store the input list, the target element K, and the result of the calculation. It does not create any new data structures or use any additional memory. Therefore, the space used by the code remains constant regardless of the input size.

Approach#3: Using filter()+lambda()

We use the filter() function and a lambda function to filter the tuples from the list that contain the given element K. The lambda function checks if K lies between the two values of each tuple. If multiple tuples contain the element K, we select the first one.

Algorithm

1. Initialize an empty list result.
2. Iterate over the range from 0 to the length of test_list.
3. Apply a lambda function to filter the tuples that contain the given element K.
4. Return the index of the first tuple in the filtered list.

3

Time complexity: O(n), where n is the length of test_list. This is because we are iterating over the list once to filter the tuples.

Auxiliary Space: O(1). We are not using any extra space apart from some variables to store the results.