LeetCode 704 Binary Search

    
        标签：
        
            二分搜索
        
            LeetCode
        
    发布于：2022-02-02 22:20:34
    编辑于：2022-02-05 16:55:00
    浏览量：752

题目分析

https://leetcode.com/problems/binary-search/

迭代法

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0;
        int r = nums.size() - 1;
        while (r >= l) {
            int m = (l + r) / 2;
            if (nums[m] == target) {
                return m;
            } else if (nums[m] < target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return -1;
    }
};

递归法

class Solution {
public:
    int search(vector<int>& nums, int target) {
        return helper(nums, target, 0, nums.size() - 1);
    }
    
    // should check both ends
    int helper(vector<int>& nums, int target, int l, int r) {
        if (r < l) return -1;
        int m = (l + r) / 2;
        if (nums[m] == target) return m;
        if (nums[m] < target) return helper(nums, target, m + 1, r);
        if (nums[m] > target) return helper(nums, target, l, m - 1);
        return -1;
    }
};

Links: leetcode-704-binary-search