最小交换，以便可以应用二进制搜索

给定一个长度为n的未排序数组和一个整数k，在使用二进制搜索之前，找到最小交换以获得k的位置。在这里，我们可以随意交换任意两个数字。如果我们无法通过交换元素获得位置，请打印“-1”。 例如：

Input : arr = {3, 10, 6, 7, 2, 5, 4}        k = 4Output : 2Explanation :Here, after swapping 3 with 7 and 2 with 5, the final array will look like {7, 10, 6, 3, 5, 2, 4}.Now, if we provide this array to binary search wecan get the position of 4.Input : arr = {3, 10, 6, 7, 2, 5, 4}        k = 10Output : -1Explanation :Here, we can not get the position of 10 if we provide this array to the binary search even not with swapping some pairs.

方法： 在讨论方法之前，我们必须假设这里我们不应该交换对。我们只需要计算交换的最小数量，这样，如果我们将新创建的数组提供给二进制搜索，我们就可以得到k的位置。为此，我们需要将给定的数组传递给二进制搜索，并关注以下事项：-

• 在进行二进制搜索之前，我们需要计算最小元素的数量，即。 num_min k和最大元素数，即。 num_max 这里，num_min表示k中较小的可用元素的数量，num_max表示可以用于交换的较大可用元素的数量
• 这个 k的实际位置 在给定的数组中。

下面是在实现二进制搜索过程中出现的测试用例：- 案例1： 如果arr[mid]大于k，但k的位置大于mid。二进制搜索将把我们带到（arr[0]到arr[mid-1]）。但实际上我们的元素介于（arr[mid+1]到arr[last element]）之间。所以，为了朝正确的方向发展，我们需要一个比k小的东西，这样我们就可以用arr[mid]交换它，我们可以在arr[mid+1]到arr[last_元素]之间切换。所以，这里我们需要一个交换，即。 最低需要量 . 案例2： 如果arr[mid]小于k，但k的位置小于mid，则二进制搜索将把我们带到（arr[mid+1]到arr[last_element]）。但实际上我们的元素介于（arr[0]到arr[mid-1]）之间。所以，为了朝正确的方向发展，我们需要一个大于k的值，这样我们就可以用arr[mid]交换它，并且可以在arr[0]到arr[mid-1]之间切换。所以，这里我们需要一次交换，即。 最大需要量 . 案例3： 如果arr[mid]大于k，并且k的位置小于mid。现在，在这种情况下，二进制搜索可以正常工作。但是等等，这是我们必须努力解决的重要问题。正如我们所知，在这种情况下，二进制搜索会很好地工作，arr[mid]位于正确的位置，因此这不会在任何交换中使用，所以这里我们必须减少其较大的可用元素之一，即从num_max开始。当arr[mid]小于k且k的位置大于mid时，情况也是如此。在这里，我们必须减少其较小的可用元素之一，即从num_min开始。 案例4： 如果arr[mid]==k或pos==mid，那么我们可以很容易地从二进制搜索中得出结果。 所以，到目前为止，我们已经计算了 最低需要量 i、 e.交换所需的最小元件数量， 最大需要量 i、 e.交换所需的最大元件数量， 最大数 i、 e.k中仍可用于交换的较大元素的总数，以及 num_min i、 e.k中可交换的最小元素总数。 现在我们必须考虑两种情况： 案例1： 如果最小需求大于最大需求。在这种情况下，我们必须用k中较小的替换所有这些所需的最大元素。所以我们必须使用num_min中较小的元素。现在所有所需的最大替换都完成了。这里最重要的是，当我们用较小的元素替换所有这些需要的最大元素时，这些较小的元素得到了正确的位置。因此，我们间接地做了一些所需的较小元素交换，这将被计算为 最低需求–最高需求 此外，还将提供num_min num_min–需要的最大值 .现在，我们必须计算剩余的最低掉期需求。如果我们有足够的num_min，即num_min>need_minimum，我们可以计算这些互换。在这种情况下，互换将被取消 最大需要量+最小需要量 否则它将是-1。同样的概念也适用于需求最小值小于需求最大值的情况。 以下是上述方法的基本实施：-

输出：

2