C++ binary search, easy to understand


  • 0
    class Solution {
        int findPos(vector<int>& nums, int target) {
            int s = 0;
            int e = nums.size();
            
            while(s < e) {
                int mid = (s + e) / 2;
                
                if(nums[mid] == target) {
                    return mid;
                } else if(nums[mid] > target) {
                    e = mid;
                } else if (nums[mid] < target) {
                    s = mid + 1;
                }
            }
            
            return -1;
        }
    public:
        vector<int> searchRange(vector<int>& nums, int target) {
            int pos = findPos(nums, target);
            if (pos == -1)
                return vector<int>{-1, -1};
            
            int left = pos - 1;
            int right = pos + 1;
            bool con = true;
            
            while(con) {
                con = false;
                if(right < nums.size() && nums[right] == target) {
                    right ++;
                    con = true;
                }
                if(left >= 0 && nums[left] == target) {
                    left --;
                    con = true;
                }
            }
            
            return vector<int>{left + 1, right - 1};
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.