- LinkList
search an element in a sorted and rotated array in python
Search an element in a sorted and rotated array is using Binary search method,Find an element in a sorted and rotated array using the binary search method, see how it works,We are using the same concept but different ideas,We will divide the array into 2 sub array and So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Devise a way to find an element in the rotated array
Algo:
- 1 Find middle point mid in array/list = (l + r)//2
- 2 If key is present at middle point is equal so the return mid.
- 3 If key>=arr[l] and key<=arr[mid] a) If key to be searched lies in range from arr[l] to arr[mid], recur for arr[l..mid].
- 4 if key>=arr[mid] and key<=arr[r] a) If key to be searched lies in range from arr[mid+1] to arr[h], recur for arr[mid+1..h].
b) Else recur for arr[mid+1..h]
b) Else recur for arr[l..mid]
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def search(arr,l,r,key): | |
| if l > r: | |
| return -1 | |
| mid = (l + r) // 2 | |
| if arr[mid] == key: | |
| return mid | |
| if arr[l] <= arr[mid]: | |
| if key >= arr[l] and key <= arr[mid]: | |
| return search(arr, l, mid-1, key) | |
| return search(arr, mid+1, r, key) | |
| if key >= arr[mid] and key <= arr[r]: | |
| return search(arr, mid+1, r, key) | |
| return search(arr, l, mid-1, key) | |
| arr=[4,5,6,7,9,10,1,2,3]; | |
| key=7; | |
| obj=search(arr,0,len(arr)-1,key); | |
| if obj==-1: | |
| print('not found'); | |
| else: | |
| print('element in list is position ',obj+1) |
