Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

When to use "=" in binary search condition?

I am quite confused about the scenarios when to use the = in binary search. For example, this is what i found from wiki, in which it is using while (imin <= imax)

int binary_search(int A[], int key, int imin, int imax)
{
  // continue searching while [imin,imax] is not empty
  while (imin <= imax)
    {
     int imid = midpoint(imin, imax);
  if (A[imid] == key) 
    return imid;
  else if (A[imid] < key)
     imin = imid + 1;
  else        
    imax = imid - 1; 
    }

  return KEY_NOT_FOUND;
}

However, I also found a lot of code using something like

while (imin < imax)

My questions are: what's the concern to use the = or not? Any reason behind?

Thanks so much!

like image 214
skydoor Avatar asked Feb 24 '16 21:02

skydoor


People also ask

How do you know when to use binary search?

In its simplest form, binary search is used to quickly find a value in a sorted sequence (consider a sequence an ordinary array for now). We'll call the sought value the target value for clarity. Binary search maintains a contiguous subsequence of the starting sequence where the target value is surely located.

What is the necessary condition for a set in order to use a binary search?

When you use a binary search function you must ensure that the input is sorted, and sorted to the order you're going to use. If these two are not met - you're not required to provide correct result.

What is the condition of binary search algorithm?

Binary search is a fast search algorithm with run-time complexity of Ο(log n). This search algorithm works on the principle of divide and conquer. For this algorithm to work properly, the data collection should be in the sorted form.


1 Answers

Note these two algorithms on wiki:

Iterative binary search:

int binary_search(int A[], int key, int imin, int imax)
{
  // continue searching while [imin,imax] is not empty
  while (imin <= imax)
    {
      // calculate the midpoint for roughly equal partition
      int imid = midpoint(imin, imax);
      if (A[imid] == key)
        // key found at index imid
        return imid;
      // determine which subarray to search
      else if (A[imid] < key)
        // change min index to search upper subarray
        imin = imid + 1;
      else        
        // change max index to search lower subarray
        imax = imid - 1;
    }
  // key was not found
  return KEY_NOT_FOUND;
}

Iterative binary search with deferred detection of equality:

int binary_search(int A[], int key, int imin, int imax)
{
  // continually narrow search until just one element remains
  while (imin < imax)
    {
      int imid = midpoint(imin, imax);

      // code must guarantee the interval is reduced at each iteration
      assert(imid < imax);
      // note: 0 <= imin < imax implies imid will always be less than imax

      // reduce the search
      if (A[imid] < key)
        imin = imid + 1;
      else
        imax = imid;
    }
  // At exit of while:
  //   if A[] is empty, then imax < imin
  //   otherwise imax == imin

  // deferred test for equality
  if ((imax == imin) && (A[imin] == key))
    return imin;
  else
    return KEY_NOT_FOUND;
}

You have three cases to consider, when imin < imax, imin == imax and imin > imax. The first algorithm deals with less than and equality within the while loop, whereas in the second algorithm, the equality case is deferred to the if statement. As wiki states:

The iterative and recursive versions take three paths based on the key comparison: one path for less than, one path for greater than, and one path for equality. (There are two conditional branches.) The path for equality is taken only when the record is finally matched, so it is rarely taken. That branch path can be moved outside the search loop in the deferred test for equality version of the algorithm.

The deferred detection approach foregoes the possibility of early termination on discovery of a match, so the search will take about log2(N) iterations. On average, a successful early termination search will not save many iterations. For large arrays that are a power of 2, the savings is about two iterations. Half the time, a match is found with one iteration left to go; one quarter the time with two iterations left, one eighth with three iterations, and so forth. The infinite series sum is 2.

The deferred detection algorithm has the advantage that if the keys are not unique, it returns the smallest index (the starting index) of the region where elements have the search key. The early termination version would return the first match it found, and that match might be anywhere in region of equal keys.

So the use of either <= in a while loop, or simply <, will depend on your choice of implementation.

like image 120
assefamaru Avatar answered Oct 27 '22 13:10

assefamaru