Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def shifted_arr_search(shiftArr, num):
- def binary_search(arr, left, right, num):
- if right < left:
- return -1
- m = (left+ right) / 2
- if arr[m] == num:
- return m
- if arr[m] > num:
- return binary_search(arr, left, m - 1, num)
- else:
- return binary_search(arr, m + 1, right, num)
- def rec(left, right, arr, num):
- if left > right:
- return -1
- else:
- m = (left + right) / 2
- mid_number = shiftArr[m]
- if mid_number == num:
- return m
- if mid_number > shiftArr[left]:
- # shiftArr[l:m] is a sorted array
- # apply normal binary search if num is in this interval
- if num >= shiftArr[left] and num < mid_number:
- return binary_search(arr, left, m - 1, num)
- elif shiftArr[right] > mid_number:
- # shiftArry[m:right] is a sorted array
- # apply normal binary search if num is in this interval
- if num > mid_number and num <= shiftArr[right]:
- return binary_search(arr, m + 1, right, num)
- if mid_number > shiftArr[right]:
- # the pivot is in shiftARr[m:right]
- # if num is in this interval then i apply rec for this interval
- if num <= shiftArr[right]:
- return rec(m + 1, right, arr, num)
- elif shiftArr[left] > mid_number:
- # the pivot is in shiftArr[left:m]
- # if num is in this interval then I apply rec for this interval
- if num <= shiftArr[mid]:
- return rec(left, m - 1, arr, num)
- return -1
- return rec(0, len(shiftArr) - 1, shiftArr, num)
- shiftArr = [9, 12, 17, 2, 4, 5]
- num = 6
- print shifted_arr_search(shiftArr, num)
Add Comment
Please, Sign In to add comment