Leetcode 34 Search for a Range (二分搜索 lower_bound和upper_bound)

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm‘s runtime complexity must be in the order ofO(logn).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

题目链接：https://leetcode.com/problems/search-for-a-range/

题目大意：找到数字value在排序好的nums中的最左最右位置

题目分析：直接对C++ STL中的lower_bound和upper_bound函数进行修改

public class Solution {
    
    //找nums中第一个等于target的数字
    int myLowerBound(int[] nums, int sz, int target) {   
        int ans = -1;
        int fir = 0, mid = 0, half = 0, len = sz;
        while(len > 0) {
            half = len >> 1;
            mid = fir + half;
            if(nums[mid] < target) {
                fir = mid + 1;
                //mid处的也要减去
                len = len - half - 1;
            }
            else {
                if(nums[mid] == target) {
                    ans = mid;
                }
                len = half;
            }
        }
        return ans;
    }
    
    //找nums中最后一个等于target的数字
    int myUpperBound(int[] nums, int sz, int target) {
        int ans = -1;
        int fir = 0, mid = 0, half = 0, len = sz;
        while(len > 0) {
            half = len >> 1;
            mid = fir + half;
            if(nums[mid] <= target) {
                fir = mid + 1;
                //mid处的也要减去
                len = len - half - 1;
            }
            else {
                if(mid != 0 && nums[mid - 1] == target) {
                    ans  = mid - 1;
                }
                len = half;
            }
        }
        if(mid == sz - 1 && nums[mid] == target) {
            ans = sz - 1;
        }
        return ans;
    }
    
    public int[] searchRange(int[] nums, int target) {
        int len = nums.length;
        int[] ans = {-1, -1};
        if(nums[len - 1] < target || nums[0] > target) {
            return ans;
        }
        ans[0] = myLowerBound(nums, len, target);
        ans[1] = myUpperBound(nums, len, target);
        return ans;
    }
}

C++中的lower_bound:

template <class ForwardIterator, class T>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator it;
  iterator_traits<ForwardIterator>::difference_type count, step;
  count = distance(first,last);
  while (count>0)
  {
    it = first; step=count/2; advance (it,step);
    if (*it<val) {                 // or: if (comp(*it,val)), for version (2)
      first=++it;
      count-=step+1;
    }
    else count=step;
  }
  return first;
}

upper_bound:

template <class ForwardIterator, class T>
  ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator it;
  iterator_traits<ForwardIterator>::difference_type count, step;
  count = std::distance(first,last);
  while (count>0)
  {
    it = first; step=count/2; std::advance (it,step);
    if (!(val<*it))                 // or: if (!comp(val,*it)), for version (2)
      { first=++it; count-=step+1;  }
    else count=step;
  }
  return first;
}

Leetcode 34 Search for a Range (二分搜索 lower_bound和upper_bound)

原文：http://blog.csdn.net/tc_to_top/article/details/52204833