当数组中有重复项时，如何在.NET中使用二进制搜索找到最左边或最右边的元素？是的，这里有二进制搜索，但是如果有重复的搜索就不方便了。
Array.BinarySearch()返回某个元素的索引，该索引等于搜索到的元素的索引，即，如果找到的第一个元素的索引，则该索引出现。来自文档：
允许重复的元素。如果Array包含多个等于value的元素，则该方法仅返回其中一个事件的索引，而不一定返回第一个事件的索引。
这里是一个例子。我们有一个数组1 1 1 2 2 2 3 3 3。该方法应始终返回最左边的出现，即对于2，它返回3，对于3-6，等等。
它的便捷实现存在于Python bisect.bisect_left中，我想知道为什么臭名昭著的.NET没有这样的实现？
是的，我们可以使用e和e-1两次运行二进制搜索两次，但是如果像上面的示例那样我们有很多相邻的重复项怎么办？然后一个人可以向左移动，但是如果有很多重复项怎么办？
public int BinarySearchLeft<T>(IList<T> array,T element)
where T : IComparable
{
int lo = 0;
int hi = array.Count();
while (lo < hi)
{
int mid = (lo+hi) / 2;
if (array[mid].CompareTo(element) < 0)
lo = mid + 1;
else
hi = mid;
}
return lo;
}
如果遍历一次，则可以创建一个辅助数组来阻止遍历该项目！这个想法很简单-
找到键后，将其标记为遍历（这样，如果第二次获得相同的项目，则可以识别出是否遍历了相同的索引项，因此可以使用dfs）：布尔数组。并继续这样做，直到获得不是您的“钥匙”的物品；
1.1如果找到了该项目，请检查当前索引是否小于或小于先前找到的索引（对于最左边的索引），如果是，则将其替换为当前索引。
1.2如果找到了该项目，请检查当前索引是否大于或等于先前找到的索引（对于正确的索引）（如果是），将其替换为当前索引。
对其余项目使用常规的二进制搜索算法。
遍历整个数组后，将返回最左边和最右边的索引对。
在这里，是上述方法的实现：[在Java中]
public class LeftRightMostOcc {
static class Pair{
int left,right;
// initial value for left and right pair
public void setLeftMostPair() {
this.left = Integer.MAX_VALUE;
}
public void setRightMostPair() {
this.right = Integer.MIN_VALUE;
}
}
private static Pair binarySearchUtil(int [] a,int key,int low,int high,boolean [] visited,Pair obj) {
if(high >= low) {
int middle = low + ((high-low)/2);
// found key,and not visited before
if(a[middle] == key && !visited[middle]) {
// update if less value you get,for left pair
if(middle < obj.left)
obj.left = middle;
// update if right value you get,for right pair
if(middle > obj.right)
obj.right = middle;
// mark the index
visited[middle] = true;
// keep on doing this,until you get an item which is not your "key"
Pair flag = binarySearchUtil(a,key,low,middle-1,visited,obj);
if(flag != null)
flag = binarySearchUtil(a,middle+1,high,obj);
}
// apply regular binary search algo for the rest of the item.
else if(a[middle] > key) {
return binarySearchUtil(a,obj);
}
else {
return binarySearchUtil(a,obj);
}
}
return obj;
}
private static Pair binarySearch(int [] a,int high) {
boolean [] visited = new boolean[a.length];
Pair object = new Pair();
object.setLeftMostPair();
object.setRightMostPair();
return binarySearchUtil(a,object);
}
public static void main(String[] args) {
int [] a = {1,1,2,3,4,5,5};
Pair object = binarySearch(a,a.length-1);
System.out.println("LeftMost Index: "+object.left+" - RightMost Index: "+object.right);
}
}
O / P：LeftMost指数：3-RightMost指数：6 [对于键-2]
O / P：LeftMost指数：10-RightMost指数：10 [对于键-4]
O / P：LeftMost指数：11-RightMost指数：14 [对于键-5]
,您可以通过提供修改的键比较函数来解决此问题，如果两个被比较元素相等并且与前一个元素的比较也返回相等，则返回值更大。这样，只有运行的第一个元素将返回等于。
这有点做作，可以更好地实现您自己的搜索功能。