To search an element in a sorted array in Python, create a program.
One of the intriguing difficulties with the sorted array will be solved in this session. However, there is a catch: the array given may be rotated at a particular index position. It implies that the array’s sparse items, which could be rotated at the specified index. Let’s understand the following problem statement in order to better grasp it.
Statement of the Issue
List1 has an array that is sorted ascendingly with unique values. In order to produce the array [list1[k], list1[k+1],…, list1[n-1], list1[0], list1[1],…, list1[k-1]], it can be rotated at an unknown pivot index k (1 = k list1.length). ( 0-indexed ).
Consider the following array: [4, 5, 6, 7, 8, 9, 10, 11]. It might be rotated at pivot index 3 to become [8, 9, 10, 11, 4, 5, 6, 7].
Given an integer target and an array list1 after any possible rotations, return the target’s index; if it doesn’t exist, return -1. Example No. 1
list1 = [4, 5, 6, 7, 0, 1, 2], target = 0 as an input 4 output examples, example 2
List1 = [4, 5, 6, 7, 0, 1, 2], goal = 3 as an input. Output: -1
We will now determine the ideal strategy to address this issue. Although the question is a little challenging, if we analyze the solution, we can quickly write the code. Let’s examine the next possible solution.
Solution
Since the binary search algorithm is simple and effective at finding an element, we first consider implementing it to solve search-related problems. Although the array in our situation is sorted but rotated in some places, the given list must still be sorted. Take a look at the following array. list1 = [4, 5, 6, 7, 0, 1, 2]
If we pay close attention, we can see that the rotation index is 3, and the normal array will be [0, 1, 2, 4, 5, 6, 7].
The array may now see that it has been divided into two pieces, with the right part being sorted as [0, 1, 2], and the left part being sorted as [4, 5, 6, 7].
Let’s use a graph to visualize it and use the binary search technique to solve this issue.
We create a simple graph with a basic growing line that is always going up, even if it may not be linear.
order.
As a result, the new graph will be created as
below.
We can now identify a pattern that will enable us to create the answer. We are aware that the binary search has three possible outcomes: left, right, and mid. The array consists of two sections that are both separately sorted. As far as we are aware, the binary search has three pointers: left, right, and mid.
If the target value in the given array [4, 5, 6, 7, 0, 1, 2] is 0, and the midpoint is 6, then the target value will not be exited on the left side.
We may now search the right-side element. What happens if the target value is below the midpoint?
How do we choose which side of the equation to search for when 4, 5, and 0 are less than 6 and 1, 2, respectively?
Check the value that is farthest to the left in the list; if it is less than the goal value, we don’t need to search farther to the left.
The search will start from mid + 1 and move to the right side. However, if the target value is higher than the value on the left, we search the element there.
Consider now that the midpoint is 1, with 0 being the sole element below this number. As a result, the search will take place on the left. If the leftmost value is bigger than the rightmost value, we check it and compare it to the target value. Let’s put Python code to use to implement it.
Note: We can use a comparison with the middle value’s leftmost value to determine if the middle value belongs to the left section or the right. The mid-value must belong to the left section and vice versa if it is greater than the leftmost value.
Code in Python
–
class Solution:
def search(self, list1: List[int], target: int) -> int:
l, r = 0, len(list1) - 1
while l<=r:
mid = (l + r) // 2
if target == list1[mid]:
return mid
# left sorted portion
if list1[l] <= list1[mid]:
if target > list1[mid] or target < list1[l]:
l = mid + 1
else:
r = mid - 1
else:
if target < list1[mid] or target > list1[r]:
r = mid - 1
else:
l = mid + 1
return -1
list1 = [4, 5, 6, 7, 0, 1, 2]
target = 0
obj = Solution()
print("The element is at the", obj.search(list1, target), "index")
Results in:
The element is at the 4 index
Although it can appear a little difficult at first, the idea is simple. It will be obvious.
Complexity of Time
Because binary search takes log n comparisons to discover the element, the time complexity will be O(logN). Since we don’t need the additional space, the space complexity will be O(1).