算法-二分法

二分法主要是通过左右逼近的方式，向目标值靠拢，并且取得对数复杂度的算法。

下面这段代码就是一般二分法的代码，不过应该如何理解二分法的本质呢？

def search(self, nums: List[int], target: int) -> int:
	left, right = 0, len(nums) - 1
	while left <= right: 
		mid = left + (right - left)//2
		if nums[mid] < target: # select1 [<, <=]
			left = mid + 1
		else:
			right = mid - 1
	return left # select2 left, right

在做题的时候经常会对上面的选择部分感到迷惑，在具体情况下应该怎么选择呢？

我先设定一个数组——>[1,2,3,5,6,6,6,6,8,8,9]

首先我们要先明确一个概念，在while left <= right这个条件下，我们要确保数组的完整性，所以left, right = 0, len(nums) - 1，这样可以保证index的取值空间为[0, len(nums) - 1]这个闭区间。其次while的终止条件如下面表格所示：

1	2	3	5	6	6	6	6	8	8	9
L					M					R
				R	L

由表格可见，在左右指针交换位置的时候终止循环。那么L和R指针分别的意义是什么呢？

场景1：寻找小于target的位置，则目标位置是6，index为3

则在终止循环前的一个循环时L,R的位置如下：

如果select1为<时，等价于求<6和first>=6，如下所示：

1	2	3	5	6	6	6	6	8	8	9
L										R
L				R						R
			L	R
				L,R
			R	L

如果select1为<=时，等价于求 >6 和last <= 6，如下所示：

1	2	3	5	6	6	6	6	8	8	9
L										R
						L				R
						L	R
							L,R
							R	L

场景1：寻找小于target的位置

场景2：寻找大于target的位置

场景3：寻找小于等于target的首次出现的位置

场景4：寻找小于等于target的末次出现的位置

// 模板
int BinarySearch(int *arr, int arrSize, int target) 
{
    int left = 0;
    int right = arrSize - 1;
    int mid;

    while (left <= right) {
        mid = left + (right - left) / 2;
        if (arr[mid] < target) { // select [<, <=]
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return right; // select [left, right]
}
// 4种场景对应的代码：
// 场景1：< 6
int BinarySearchLowerTarget(int *arr, int arrSize, int target) 
{
    int left = 0;
    int right = arrSize - 1;
    int mid;

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

    return right;
}

// 场景2：> 6
int BinarySearchHigherTarget(int* arr, int arrSize, int target) 
{
    int left = 0;
    int right = arrSize - 1;
    int mid;

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

    return left;
}

// 场景3：<=6, 取首
int BinarySearchFirstLowerEqualTarget(int* arr, int arrSize, int target) 
{
    int left = 0;
    int right = arrSize - 1;
    int mid;

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

    return left;
}

// 场景4：<=6, 取尾
int BinarySearchLastLowerEqualTarget(int* arr, int arrSize, int target) 
{
    int left = 0;
    int right = arrSize - 1;
    int mid;

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

    return right;
}

总结：

1. L一定是要+1，R一定是-1，因为区间要不断收缩才能退出，如果没有+1，和-1，会导致死循环风险。

2. while (left <= right)中的退出条件是，left > right,出现了翻转，此时right跑到left左边。

3. 正对4种场景只需要修改if中的符号和返回值。