搜索区间-二分查找

给定一个包含 n 个整数的排序数组，找出给定目标值 target 的起始和结束位置

1、查找target的起始位置

    int searchStartPos(vector<int> vec, int target) {
        int low = 0;
        int high = vec.size() - 1;
        while (low < high) {  //注意不是 <=, 不然会死循环
            int mid = (low + high) / 2;
            if (vec[mid] >= target) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        if (vec[high] == target) {
            return high;
        } else {
            return -1;
        }
    }

2、查找target的结束位置

    int searchEndPos(vector<int> vec, int target) {
        int low = 0;
        int high = vec.size() - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            if (vec[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }

        if (vec[low - 1] == target) {
            return low - 1;
        } else {
            return -1;
        }
    }

leetcode 61. 搜索区间:
给定一个包含 n 个整数的排序数组，找出给定目标值 target 的起始和结束位置。
https://www.lintcode.com/problem/search-for-a-range/description
leetcode 462. 目标出现总和:
给一个升序的数组，以及一个target，找到它在数组中出现的次数。
https://www.lintcode.com/problem/total-occurrence-of-target/description