Binary Search Sqrt

One of the most selected algorithms in the last century is binary search. It is a general search method which is simple and efficient. It can be used to accelerate the search if the domain is continous (sorted, ascending or non-ascending order). Binary search is considered generaly faster than linear search i.e. in linear search, the average comparisons to made in an array that has elements (with uniform probablity for every element) is roughly . However, using binary search reduces the time complexity to .

Binary search can be implemented in iterative or recursive, with the psuedo code given below. [from wiki]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

int binary_search(int A[], int key, int imin, int imax)
{
  // test if array is empty
  if (imax < imin):
    // set is empty, so return value showing not found
    return KEY_NOT_FOUND;
  else
    {
      // calculate midpoint to cut set in half
      int imid = (imin + imax) / 2;
 
      // three-way comparison
      if (A[imid] > key):
        // key is in lower subset
        return binary_search(A, key, imin, imid-1);
      else if (A[imid] < key):
        // key is in upper subset
        return binary_search(A, key, imid+1, imax);
      else:
        // key has been found
        return imid;
    }
}

int binary_search(int A[], int key, int imin, int imax)
{
  // test if array is empty
  if (imax < imin):
    // set is empty, so return value showing not found
    return KEY_NOT_FOUND;
  else
    {
      // calculate midpoint to cut set in half
      int imid = (imin + imax) / 2;
 
      // three-way comparison
      if (A[imid] > key):
        // key is in lower subset
        return binary_search(A, key, imin, imid-1);
      else if (A[imid] < key):
        // key is in upper subset
        return binary_search(A, key, imid+1, imax);
      else:
        // key has been found
        return imid;
    }
}

The above is in elegant recursive form, which can be improved to non-recursive one.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

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

Two search limites (upper and lower) are defined, which narrows the search range as iterations go on progressively. Another variation of implementation is to defer the detection of equality, which only uses one condition check per iteration.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

// inclusive indices
//   0 <= imin when using truncate toward zero divide
//     imid = (imin+imax)/2;
//   imin unrestricted when using truncate toward minus infinity divide
//     imid = (imin+imax)>>1; or
//     imid = (int)floor((imin+imax)/2.0);
int binary_search(int A[], int key, int imin, int imax)
{
  // continually narrow search until just one element remains
  while (imin < imax)
    {
      int imid = (imin + imax) / 2;
 
      // 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;
}

// inclusive indices
//   0 <= imin when using truncate toward zero divide
//     imid = (imin+imax)/2;
//   imin unrestricted when using truncate toward minus infinity divide
//     imid = (imin+imax)>>1; or
//     imid = (int)floor((imin+imax)/2.0);
int binary_search(int A[], int key, int imin, int imax)
{
  // continually narrow search until just one element remains
  while (imin < imax)
    {
      int imid = (imin + imax) / 2;
 
      // 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;
}

[The deferred detection approach foregoes the possibility of early termination on discovery of a match, so the search will take about 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.]

Binary search can be used in many application domains. For example, we can use binary search to compute the square root of a number because we know that any given two numbers and (, we know that . In other words, the search domain for sqrt is continous. It is therefore applicable to use binary search. e.g. if not, we may need to sort the domain first.

#!/usr/bin/env python
# https://helloacm.com
def binsqrt(n):
    sgn = 0
    if n < 0:
        n = -n
        sgn = -1
    low = 0.0
    upp = n
    mid = (low + upp) * 0.5
    while True:
        if mid * mid > n:
            upp = mid
        else:
            low = mid
        last = mid
        mid = (upp + low) * 0.5
        if abs(mid - last) < 1e-9:
            break
    if sgn < 0:
        return complex(0, mid)
    return mid

if __name__ == "__main__":
    print binsqrt(81)

The above Python code first defines the search range to and narrows the range progressively by checking , the loop breaks if the required precision is obtained, compared to the previous value (not much has changed since last iteration).

The output is closed to the math answer 9.

9.00000000046

The error is acceptable in most cases. i.e. You may try to adjust the epsilon value to a smaller number according to your needs.

It is also noted that this python function can also deal with negative sqrt input, which will return a complex number, for example, binsqrt(-16) will returns the following.

4.00000000093j

The complex number can be defined in Python using two methods. First, in the form of a + bj, where a and b are constants. The second is to use complex(a, b). For example, 2 + 3j is equivalent to complex(2, 3)

The complex number is very convenient, for example, you can use abs() to compute its length.

# 3.60555127546
print abs(complex(2,3))

–EOF (The Ultimate Computing & Technology Blog) —