对于k

Question

的第一次出现的二进制搜索我有代码，搜索一个排序后的数组，并返回k的第一次出现的索引。 我想知道是否它可以编写使用

while(left<right) 

，而不是

while(left<=right) 

下面这段代码是全码：

public static int searchFirstOfK(List<Integer> A, int k) { 
    int left = 0, right = A.size() - 1, result = -1; 
    // A.subList(left, right + 1) is the candidate set. 
    while (left <= right) { 
     int mid = left + ((right - left)/2); 
     if (A.get(mid) > k) { 
     right = mid - 1; 
     } else if (A.get(mid) == k) { 
     result = mid; 
     // Nothing to the right of mid can be the first occurrence of k. 
     right = mid - 1; 
     } else { // A.get(mid) < k 
     left = mid + 1; 
     } 
    } 
    return result; 
} 

我如何知道何时使用左边是小于或等于正确的，或者只是使用左边是不正确的。

Answer 1

大厦：How can I simplify this working Binary Search code in C?

如果你想找到第一个出现的位置，你不能当你找到一个匹配的元素停止。您的搜索应该是这样的（当然这个假设列表进行排序）：

int findFirst(List<Integer> list, int valueToFind) 
{ 
    int pos=0; 
    int limit=list.size(); 
    while(pos<limit) 
    { 
     int testpos = pos+((limit-pos)>>1); 

     if (list.get(testpos)<valueToFind) 
      pos=testpos+1; 
     else 
      limit=testpos; 
    } 
    if (pos < list.size() && list.get(pos)==valueToFind) 
     return pos; 
    else 
     return -1; 
} 

请注意，我们只需要做好每次迭代一个比较。二进制搜索找到所有前面的元素都小于valueToFind且以下所有元素都大于或等于的唯一位置，然后然后它检查您正在查找的值是否实际存在。

链接的答案突出了以这种方式编写二进制搜索的几个优点。

Answer 2

简而言之号

考虑仅具有一个元件阵列的情况下，即，{0}和要搜索的元件是0为好。

在这种情况下，left == right，但是如果您的条件是while(left<right)，那么searchFirstOfK将返回-1。

---

这个答案是在发布代码的情况下。如果我们谈论的替代品，这样我们就可以使用while(left<right)然后马特TIMMERMANS的答案是正确的，是一个更好的办法。

下面是马特的comparison（OP - 我们称之为普通二进制）和马特TIMMERMANS（我们称之为优化的二进制）接近含有0 500万之间和值的列表：

Answer 3

这是一个非常有趣的问题。事情是有一种方式，你可以使你的二进制搜索权始终。事情是确定正确的范围并避免单个元素伸出行为。

while(left+1<right) 
{ 
    m = (left+right)/2; 
    if(check condition is true) 
     left = m; 
    else 
     right = m; 
} 

只记住关键的是你总是让左为最小的条件不令人满意元素，右为最大的条件满足的元素。这样你就不会卡住了。一旦你了解了这种方法的范围划分，你将永远不会在二分搜索中失败。

以上初始化会给你最大的满足条件的元素。

通过改变初始化，你可以得到各种元素（如小状况令人满意的元素）。这个答案，另一个二分查找问题