Binary Search

[caipengbo]

以前的相关题目记录：
Weekly Contest : #2
剑指offer: caipengbo/Coding-Interviews#33

[caipengbo]

二分查找的思想和模板

思想：有序（数组有序、范围的潜在有序）、找边界(临界点)、(尝) 试每次取到的mid(g函数的设计)

区间左闭右 [start, end ) 开模板

int start = 0, end = length - 1; 
while(start < end) {
        mid = start + (end - start) / 2;
        if g(mid)  
            end = mid ;  // 左侧
        else
            start = mid + 1;  // 右侧
}
return start;  // or how to use upper bound (start) 

• 首先明确我们是对索引进行二分还是对值进行二分（有时忘记是索引，导致马虎出现bug）
• 注意初始位置(start 和 end), end = length-1 和 end = length 结果是一样的（？？？n=2的时候剑指offer P3.2题），用作数组下标的时候最好使用 end = length-1
• g( ) 函数：最终返回的是，第一个满足g(m) == true的元素下标m(注意end = mid 在前面时)
• 返回 start, 找不到时，会返回左边界或者右边界(上图说的不太对)

[caipengbo]

两种搜索方式

(数组的) 索引搜索 和 (范围的) 值搜索

索引搜索

• 注意不要越界（一般end初始为len-1不会越界）
• 注意最终返回的start，如何去使用它(start = 0 时，start = len-1时)

值搜索

• 值搜索一般是知道一个范围，在这个范围内进行二分搜索
• 一般搜索是在整数范围内，如果是浮点数的话，一般使用while(true)循环，然后在循环内部设置出口，这时候边界 缩小边界的时候， 使用 start=m,end=m进行缩小

[caipengbo]

如何利用边界

找不到的情况？越界问题？
例 （一个非常好的题目）
寻找有序数组中，比val值小的数的个数，注意val不一定在数组中，并且数组中可能含有重复元素

    public int findKSmallest(int[] nums, int val) {
        if (nums.length == 0) return 0;
        int l = 0, r = nums.length-1, m;
        while (l < r) {
            m = l + (r - l) / 2;
            if(nums[m] > val) r = m;
            else l = m + 1;
        }
        if (nums[l] > val) return l;  // 如何利用边界
        return l+1;
    }

例 LeetCode第34题

更多例题

如何设计 g函数(判断mid的函数)

• g函数代表第一个满足 g(m)== true时的m的取值，取不到时，会获得左右边界
• g函数实际上就是起到了一个判断的作用，这就体现了二分法中 "试"这个字的含义了

例题见

[caipengbo]

K th 问题 以及 二维问题

堆和二分查找方法

**这一点需要对比一下

行列都排序的二维数组的 Kth 问题

LeetCode：378, 668, 719, 786

如何转换成 二维问题？？ 设置两个方向的坐标i j 然后映射到 input的一维数组上

这里，g函数有一个统计的过程，通过count与K进行比较，来缩短区间

例题
240题

[caipengbo]

旋转有序数组

旋转数组中查找某值

1) everytime check if targe == nums[mid], if so, we find it.
2) otherwise, we check if the first half is in order (i.e. nums[left]<=nums[mid]) 
  and if so, go to step 3), otherwise, the second half is in order,   go to step 4)
3) check if target in the range of [left, mid-1] (i.e. nums[left]<=target < nums[mid]), if so, do search in the first half, i.e. right = mid-1; otherwise, search in the second half left = mid+1;
4)  check if target in the range of [mid+1, right] (i.e. nums[mid]<target <= nums[right]), if so, do search in the second half, i.e. left = mid+1; otherwise search in the first half right = mid-1;

旋转数组中含重复元素

The only difference is that due to the existence of duplicates,
we can have nums[left] == nums[mid] and in that case, the first half could be out of order (i.e. NOT in the ascending order, e.g. [3 1 2 3 3 3 3]) and we have to deal this case separately. In that case, it is guaranteed that nums[right] also equals to nums[mid], so what we can do is to check if nums[mid]== nums[left] == nums[right] before the original logic, and if so, we can move left and right both towards the middle by 1. and repeat.

旋转数组中的最小值

g函数 if (nums[mid] < nums[hi])

[caipengbo]

二维问题