题解 | #二分查找-II#

#include <stack>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 如果目标值存在返回下标，否则返回 -1
     * @param nums int整型vector
     * @param target int整型
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        // write code here
        if (nums.size() == 0) {
            return -1;
        } else if (nums.size() == 1 && target != nums[0]) {
            return -1;
        } else if (nums.size() == 1 && target == nums[0]) {
            return 0;
        }
        stack<int>search_first_position;
        int middle = binarysearch(nums, target);
	  //查看前面位置是否也是相等
        while (middle >= 0 && nums[middle] == target) {
		  //相等压入栈
            search_first_position.push(middle);
            middle--;
        }
        if (search_first_position.empty()) {
            return -1;
        }
        return search_first_position.top();

    }

    //二分查找搜索目标值
    int binarysearch(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int middle = (left + right) / 2;
            if (nums[middle] == target) {
                return middle;
                break;
            } else if (nums[middle] < target) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return -1;
    }
};