排序数组中值变化的二进制搜索算法

Question

我需要编写一个类似于二进制搜索的算法，但有几个例外。

问题：给出了一个整数数组，我需要找到值变化的索引。

假设：数组中只有两个可能的值，所以我们只需要担心它更改一次值。(例如，下面的示例使用0和100)

示例：

 [0,0,0,0,100,100,100,100,100,100,100,100,100,100] //search would return 4

 [0,0,0,0,0,0,0,0,100,100,100,100,100,100] //search would return 8

 [0,0,0,0,0,0,0,0,0,0,0,0,0,100] //search would return 13

解释：

不是作业问题。我有一个问题，我必须计算一个排序的日期数组，对应于一个项目在2周内的价格变化。如果这些日期结束时的价格是不同的，我想要有效地找到价格变化的确切日期。

该方法只需采用格式。

public int FindChangeIndex(int[] input){
    int changeIndex = -1

    //use efficient binary-search 
    //like algorithm to find change index

    return changeIndex;        
}

Answer 1

这只是二进制搜索的一个变化，假设一个数组只包含A和B(A != B)

input = A, A, ...B,.. B

因此，我们的任务是在输入中找到B的第一次出现。

假设输入的中间值等于B，那么B的第一次出现应该在前半部分，反之亦然。我们可以递归地执行这个搜索，直到搜索空间的大小为空为止。

假设输入的长度是n。我们有我们的伪码：

int result = n - 1;
int start = 0;
int end = n - 1;
while(start <= end){
    int mid = (start + end)/2;
    if(input[mid] == B){
        result = mid;
        end = mid - 1;
    }else{
        start = mid + 1;
    }   
}
return result;