我需要写一个看起来类似于二分查找的算法,但是 除了少数异常(exception)。
问题: 给定一个整数数组,我需要找到值发生变化的索引。
假设:
数组中只有两个可能的值,所以我们只需要担心
它改变一次值(value)。 (例如,下面的示例使用 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;
}
最佳答案
这只是二分搜索的一种变体,让我们考虑一个只包含 A 和 B (A != B) 的数组
输入 = A, A, ...B,.. B
因此,我们的任务是在输入中找到第一次出现的 B
。
假设输入的mid等于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;
关于c# - 二进制搜索算法查找排序数组中值的变化,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38058740/