Share my C++ solution with comment,easy to understand


  • 1
    V

    Binary Search:

    class Solution {
    public:
        int search(vector<int>& nums, int target) {
            int n = nums.size();
            if (n == 0) return -1;
            
            int left = 0;
            int right = n-1;
            int mid = 0;
            
            while (left <= right)
            {
                mid = left + (right-left) / 2;
                
                if (target == nums[mid])
                    return mid;
                 
                //every time we check whether the left part(array[left] ... array[mid]) is in ascending order or  the right part(array[mid] ... array[right]) is in ascending order
                if (nums[left] <= nums[mid])
                {
                    //if the left part is in ascending order, the next searthing depends on whether the target is in the left part
                    //if the target is in the range of left part(of course it may not exist in left part),it must not exist in the right part then we eliminate the right part,otherwise eliminate the left part
                    if (nums[left] <= target && target < nums[mid])
                        right = mid - 1;
                    else
                        left = mid + 1;
                }
                else
                {
                    //likewise the right part is in ascending order,we can eliminate another part just check if the target is in range of right part 
                    if (nums[mid] < target && target <= nums[right])
                        left = mid + 1;
                    else
                        right = mid - 1;
                }
            }
            
            return -1;
        }
    };

  • 0
    V
    class Solution {
    public:
        int search(vector<int>& nums, int target) {
            int n = nums.size();
            if (n == 0) return -1;
            
            int left = 0;
            int right = n-1;
            int mid = 0;
            
            while (left <= right)
            {
                mid = left + (right-left) / 2;
                
                if (target == nums[mid])
                    return mid;
                    
                if (nums[left] <= nums[mid])
                {
                    if (nums[left] <= target && target < nums[mid])
                        right = mid - 1;
                    else
                        left = mid + 1;
                }
                else
                {
                    if (nums[mid] < target && target <= nums[right])
                        left = mid + 1;
                    else
                        right = mid - 1;
                }
            }
            
            return -1;
        }
    };

Log in to reply
 

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