查找排序数组中值变化的类二分搜索算法

本文关键字：搜索算法 二分 数组 排序 变化 查找 | 更新日期: 2023-09-27 17:52:15

我需要写一个算法，似乎是类似于二进制搜索，但是除了少数例外。

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

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

示例(s): 

 [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

解释:

不是作业问题。我有一个问题，我必须计算一个排序数组与商品在两周内的价格变化相对应的日期。如果价格在这些日期结束时是不同的，我要有效地找到确切的日子价格变了。

方法的格式必须是

public int FindChangeIndex(int[] input){
    int changeIndex = -1
    //use efficient binary-search 
    //like algorithm to find change index
    return changeIndex;        
}

查找排序数组中值变化的类二分搜索算法

这只是二进制搜索的一个变体，让我们考虑一个只包含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;
相关文章：