学步园

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

思路：

参考std::lower_bound的实现：

  template<typename _ForwardIterator, typename _Tp, typename _Compare>              
    _ForwardIterator                                                                
    lower_bound(_ForwardIterator __first, _ForwardIterator __last,                  
        const _Tp& __val, _Compare __comp)                                          
    {                                                                               
      typedef typename iterator_traits<_ForwardIterator>::value_type                
    _ValueType;                                                                     
      typedef typename iterator_traits<_ForwardIterator>::difference_type           
    _DistanceType;                                                                  
                                                                                    
      // concept requirements                                                       
      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)    
      __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,                 
                  _ValueType, _Tp>)                                                 
      __glibcxx_requires_partitioned_lower_pred(__first, __last,                    
                        __val, __comp);                                             
                                                                                    
      _DistanceType __len = std::distance(__first, __last);                         
                                                                                    
      while (__len > 0)                                                             
    {                                                                               
      _DistanceType __half = __len >> 1;                                            
      _ForwardIterator __middle = __first;                                          
      std::advance(__middle, __half);                                               
      if (__comp(*__middle, __val))                                                 
        {                                                                           
          __first = __middle;                                                       
          ++__first;                                                                
          __len = __len - __half - 1;                                               
        }                                                                           
      else                                                                          
        __len = __half;                                                             
    }                                                                               
      return __first;                                                               
    }        

通过二分查找法进行。其实二分查找本身就是很难一次写好的问题。Jon Bentley在Programming Pearls就说过很少有程序员能够一波写好二分查找。

题解：

class Solution {
public:
    int searchInsert(int A[], int n, int target) {
        return lower_bound(A, A + n, target) - A;
    }
};