p "==========================Binary search========================"

def binary_search(arr, target)
  low = 0
  high = arr.length - 1

  while low <= high
    mid = low + (high - low) / 2
    if arr[mid] == target
      return mid
    elsif arr[mid] < target
      low = mid + 1
    else  
      high = mid - 1
    end  
  end

  return -1
end

p binary_search([1, 3, 5, 5, 5, 5, 67, 123, 125], 5)

p binary_search([1, 3, 5, 5, 5, 5, 67, 123, 125], 123)


p "==========================Search in Rotated sorted array========================"

# https://[Log in to view URL]

# https://[Log in to view URL]

def search_rotated_arr(arr, key)
    low = 0
    high = arr.length - 1
    
    while low <= high
      mid = (low + high) / 2
    
      if arr[mid] == key
        return mid
      elsif arr[low] <= arr[mid]
        if key >= arr[low] && key < arr[mid]
          high = mid - 1
        else
          low = mid + 1
        end
      else
        if key > arr[mid] && key <= arr[high]
          low = mid + 1
        else
          high = mid - 1
        end
      end
    end
    
    return -1
end

p search_rotated_arr([5, 6, 7, 8, 9, 10, 1, 2, 3], 1)