数据结构考试复习（3）

发表于   |  

##binary-search 二分查找

###模板

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 = midpoint(imin, imax);
      // eg:  imid = (imin+imax)>>1
 
      // 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;
    }
}

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 = midpoint(imin, imax);
      // eg: imid = (imin+imax)>>1
      
      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;
}

##STL函数

1
2
3
4
5
6
7
8
9
10
template <class ForwardIterator, class T, class Compare>
  bool binary_search (ForwardIterator first, ForwardIterator last,
                      const T& val, Compare comp);
```                      
Returns true if any element in the range [first,last) is equivalent to val, and false otherwise.
The elements are compared using operator< for the first version, and comp for the second. Two elements, a and b are considered equivalent if (!(a<b) && !(b<a)) or if (!comp(a,b) && !comp(b,a)).

The elements in the range shall already be sorted according to this same criterion (operator< or comp), or at least partitioned with respect to val.

The function optimizes the number of comparisons performed by comparing non-consecutive elements of the sorted range, which is specially efficient for random-access iterators.

template
bool binary_search (ForwardIterator first, ForwardIterator last, const T& val)
{
first = std::lower_bound(first,last,val);
return (first!=last && !(val<*first));
}
```

from http://en.wikipedia.org/wiki/Binary_search_algorithm