首页 文章

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

提问于
浏览 次
1

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

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

Assumption: 数组中只有两个可能的值，因此我们只需要担心它一次更改值 . （例如，下面的示例使用 0 和 100 ）

Example(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

Explanation:

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

该方法只需要采用格式

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

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

    return changeIndex;        
}
c# arrays algorithm search binary

1 回答

  • 3

    这只是二进制搜索的一种变体，让我们考虑一个只包含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;
    回复于

相关问题