704. Binary Search

發表於 | 分類於

problem

solution

  • normal version
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution {
    public:
        int search(vector<int>& nums, int target) {
            int n = nums.size();
            int l = 0, r = n-1;
            while(l<=r){
                int mid = l+(r-l)/2;
                if(nums[mid] == target) return mid;
                else if(nums[mid]< target) l =mid+1;
                else r= mid-1;
            }
            return -1;
        }
    };
  • left bound
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Solution {
    public:
        int search(vector<int>& nums, int target) {
            int n = nums.size();
            int l = 0, r = n;
            while(l<r){
                int mid = l+(r-l)/2;
                if(nums[mid] == target) return mid;
                else if(nums[mid]< target) l =mid+1;
                else r= mid;
            }
            if(l<n && nums[l] == target) return l;
            return -1;
        }
    };

analysis

  • time complexity O(logn)
  • space complexity O(1)