C++ binary search


  • 1
    X
    class Solution {
    public:
        bool binarysearch(vector<int>& nums, int left, int right, int target){
            while(left <= right){
                int mid = left + (right - left) / 2;
                if(nums[mid] == target){
                    return true;
                }else if(nums[mid] < target){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
            return false;
        }
        
        bool search(vector<int>& nums, int target) {
            if(nums.size() == 0){
                return false;
            }
            int low = 0, high = nums.size() - 1;
            while(low <= high){
                int mid = low + (high - low) / 2;
                if(nums[mid] == target){
                    return true;
                }
                if(nums[low] == nums[mid] && nums[high] == nums[mid]){
                    ++low;
                    --high;
                }
                else if (nums[low] <= nums[mid]) {//first half is in order
    				if (nums[mid] > target && nums[low] <= target) {
    					return binarysearch(nums, low, mid - 1, target);
    				}
    				low = mid + 1;
    			}
    			else {// second half is in order
    				if (nums[mid] < target && nums[high] >= target) {
    					return binarysearch(nums, mid + 1, high, target);
    				}
    				high = mid - 1;
    			}
            }
            return false;
        }
    };

Log in to reply
 

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