text: #!/usr/bin/python3
  
  # https://practice.geeksforgeeks.org/problems/search-in-a-rotated-array/0
  
  def binarySearchRotated(arr, l, r, k):
      """
      The logic is pretty straight forward
      If the first half is sorted check if k lies in the range else check in
      the other half
      If the first half is not sorted the second half is sorted, check in 
      both the halves as usual
      """
      mid = (l + r)//2
      while l <= r:
          if k == arr[mid]:
              return mid
          
          if arr[l] <= arr[mid]:
              if k >= arr[l] and k <= arr[mid]:
                  r = mid - 1
              else:
                  l = mid + 1
          
          else:
              if k >= arr[mid] and k <= arr[r]:
                  l = mid + 1
              else:
                  r = mid - 1
          
          mid = (l + r)//2
      
      return False
  
  arr = [5, 6, 7, 8, 9, 10, 1, 2, 3]
  arr = [239, 241, 242, 244, 246, 247, 254, 255, 256, 258, 261, 265, 267, 271, 274, 276, 281, 285, 286, 291, 293, 294, 300, 304, 314, 316, 321, 324, 326, 328, 337, 340, 341, 342, 348, 349, 351, 353, 362, 363, 369, 374, 375, 376, 377, 382, 384, 391, 392, 395, 397, 398, 399, 402, 410, 411, 424, 426, 427, 428, 430, 432, 442, 445, 448, 452, 453, 454, 460, 461, 462, 463, 465, 467, 471, 473, 474, 487, 490, 492, 495, 497, 502, 505, 515, 517, 520, 535, 536, 540, 541, 542, 544, 545, 550, 566, 568, 576, 581, 582, 586, 587, 599, 600, 603, 608, 616, 621, 633, 636, 644, 647, 653, 655, 658, 661, 663, 669, 670, 673, 678, 680, 682, 683, 685, 686, 688, 690, 692, 695, 698, 701, 702, 704, 707, 714, 715, 719, 724, 727, 728, 732, 733, 735, 737, 738, 742, 749, 751, 752, 756, 760, 763, 768, 770, 773, 774, 777, 791, 794, 803, 804, 806, 808, 824, 826, 832, 834, 836, 844, 848, 852, 853, 854, 864, 868, 872, 877, 878, 880, 881, 883, 890, 894, 895, 899, 916, 917, 918, 920, 922, 923, 925, 928, 931, 933, 940, 943, 944, 945, 948, 957, 958, 960, 961, 966, 967, 968, 969, 972, 980, 982, 983, 989, 990, 991, 996, 999, 16, 24, 27, 28, 29, 33, 37, 38, 41, 44, 47, 53, 54, 55, 58, 59, 61, 69, 74, 76, 79, 81, 83, 92, 93, 99, 110, 113, 119, 125, 126, 129, 137, 139, 141, 142, 147, 148, 149, 151, 155, 157, 161, 162, 166, 170, 173, 175, 176, 181, 186, 188, 191, 192, 194, 199, 202, 204, 210, 211, 213, 214, 218, 222, 224, 226, 229, 230, 235]
  print(binarySearchRotated(arr, 0, len(arr)-1, 239))