>

LoeiJe

:D 获取中...

何以解忧？唯有暴富

二分查找

二分查找问题

  1. 二分查找的框架

在二分查找时， 将所有的条件罗列清楚

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int binary_search(num, target) {
    int left = 0, right = {num.size or num.size - 1}, mid;
    while(...) {
        int mid = left + (right - left) / 2; // 防止溢出
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
       }
    }
   return ...;
}
  1. 在有序数组中寻找一个数
    最简单情况 查找一个相等值 返回
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int binarySearch(int[] nums, int target) {
       int left = 0;
       int right = nums.length - 1; // 对右侧赋值-1， 左闭右闭区间

       while(left <= right) {         // 判断条件 包含 l == r
           int mid = (right + left) / 2;
           if (nums[mid] < target)
               left = mid + 1; // 因为都是闭区间 所以 +１
           else if (nums[mid] > target)
               right = mid - 1; // 因为都是闭区间　所以－１
           else if(nums[mid] == target)   // 等于的情况少　
              return mid;　//　边界
           }
       return -1;
    >}
  • while条件为什么是<=,而不是<是因为在传入的right是最后一个元素下标。
    这两个条件可能出现在不同功能的二分查找中，区别是：前者相当于两端都闭区间 [left, right]，后者相当于左闭右开区间 [left, right)，因为索引大小为 nums.length 是越界的。
  • 这个算法无法计算target在数组中出现的第一个位置和最后一个位置

  1. 寻找左边界

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    int left_bound(nums, target) {
        if (nums.size == 0) return -1;
        int left = 0;
        int right = nums.size; < right 为数组最后一个元素后一个位置

        while (left < right) { // 条件是<
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                right = mid;    // 右侧开区间 检查mid
            } else if (nums[mid] < target) {
                left = mid + 1;     //左闭合 所以mid 加1
            } else if (nums[mid] > target) {
                right = mid;
            }
        }
        return left;
    }

    查找的区间为[left, right)
    函数返回的区间为[0, nums.size]最后需要添加if(left == nums.size || nums[left] != target) return -1 判断

  2. 寻找右边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int right_bound(nums, target) {
    if (nums.size == 0) return -1;
    int left = 0, right = nums.size;

    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            left = mid + 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left - 1;
}

因为在查找右侧每次修改都是mid = left + 1在返回时需要进行-1处理,其他同左

学习笔记