Keep

    Search by

    2022 第 24 周

    6/19/2022, 8:28:00 AM

    // 模版三「一般」情形2: 大于
    class Solution {
        public int search(int[] nums, int target) {
            int l = -1, r = nums.length;
            while(l + 1 < r){
                int c = l + (r - l) / 2;
                if(nums[c] <= target) l = c; // #1 更新后l及其左侧元素「必」小于等于target
                else r = c; // #2 更新后r及其右侧「必」大于target
            }
            return r == nums.length ? -1 : r; // 处理: 相等/刚好大于/不存在
        }
    }
    // 模版三「一般」情形1: 大于等于
    class Solution {
        public int search(int[] nums, int target) {
            int l = -1, r = nums.length;
            while(l + 1 < r){
                int c = l + (r - l) / 2;
                if(nums[c] < target) l = c; // #1 更新后l及其左侧元素「必」小于target
                else r = c; // #2 更新后r及其右侧「必」大于等于target
            }
            // return (r == nums.length || nums[r] != target) ? -1 : r; // 704题的返回,处理:相等/不等
            return r == nums.length ? -1 : r; // 处理: 相等/刚好大于/不存在
        }
    }
    // 模版三「相等返回」写法
    class Solution {
        public int search(int[] nums, int target) {
            int l = -1, r = nums.length;
            while(l + 1 < r){
                int c = l + (r - l) / 2;
                if(nums[c] == target) return c; // 找到目标值直接返回
                else if(nums[c] < target) l = c; // #1 更新后l及其左侧元素「必」小于target
                else r = c; // nums[c] > target #2 更新后r及其右侧「必」大于target
            }
            return -1;
        }
    }
    // 模版三「一般」情形3: 小于等于
    class Solution {
        public int search(int[] nums, int target) {
            int l = -1, r = nums.length;``
            while(l + 1 < r){
                int c = l + (r - l) / 2;
                if(nums[c] <= target) l = c; // #1 更新后l及其左侧元素「必」小于等于target
                else r = c; // #2 更新后r及其右侧「必」大于target
            }
            // return (l == -1 || nums[l] != target) ? -1 : l; // 704题的返回,处理:相等/不等
            return l;
        }
    }
    // 模版三「一般」情形4: 小于
    class Solution {
        public int search(int[] nums, int target) {
            int l = -1, r = nums.length;
            while(l + 1 < r){
                int c = l + (r - l) / 2;
                if(nums[c] < target) l = c; // #1 更新后l及其左侧元素「必」小于target
                else r = c; // #2 更新后r及其右侧「必」大于等于target
            }
            return l;
        }
    }
    Tag:
    周回顾

    Redky

    Redky,生活在北京(北漂),程序员,宅,喜欢动漫(海贼王)。"年轻骑士骑马出城,不曾见过绝望堡下森森骸骨,就以为自己可以快意屠龙拯救公主。"