LeetCode 704 Binary Search

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

题目分析

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;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/