分治算法与二分查找

一、二分查找

介绍:二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法，前提是数据结构必须先排好序，可以在数据规模的对数时间复杂度内完成查找。但是，二分查找要求线性表具有有随机访问的特点（例如数组），也要求线性表能够根据中间元素的特点推测它两侧元素的性质，以达到缩减问题规模的效果。
代码模板：

#常规
def bsearch(l, r, target):
	while l <= r:
		mid = (l + r) // 2
		if nums[mid] > target:
			right = mid - 1
		elif  nums[mid] < target:
			left = mid + 1
	return mid

'''
特殊情况：由于部分题左侧区间保留中间值（因为我们计算中间值向下取整，
这是为什么左侧区间保留中间值，右侧不保留的原因），保留中间值就需要
考虑啊是否会出现死循环的问题。
'''
def bsearch(l, r, target):
	while l <= r:
		mid = (l + r) // 2
		if nums[mid] > target:
			right = mid			#保留中间值
		elif  nums[mid] < target:
			left = mid + 1
		else:					#防止出现死循环
			break			
	return mid

举例一(leetcode33)
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。

样例：
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
解法一:一边循环直接出结果
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        #由于旋转导致一边符合升序，另一边有可能不符合升序
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target: return mid
            #等号满足区间长度为2，左侧为正确答案
            if nums[left] <= nums[mid]:	
                if nums[left] <= target <= nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] <= target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1
        
解法二：更为常规的解法
思路：两次运用二分查找，第一次寻找旋转点，第二次寻找目标值。
其中第二次直接套用模板，第一次对于边界条件考虑比较麻烦。
```python
class Solution:
    def search(self, nums, target):
    	#通过二分算法获取转折点
        def bfind_rotate(left, right):
            while left <= right:
                mid = (left + right) // 2
                if mid < len(nums) - 1 and nums[mid] > nums[mid + 1]:
                    return mid
                #由于二分往往向下取整，所以当选左侧的时候可以加上右边界
                elif nums[mid] < nums[left]:
                    right = mid				
                elif nums[right] < nums[mid]:
                    left = mid + 1
                #如果左侧区间右边界保留中间值，就需要考虑是否出现死循环
                else:
                    break
            return -1
        #通过二分算法获取目标值索引           
        def bfind(left, right, target):
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] == target:
                    return mid
                elif nums[mid] < target:
                    left = mid + 1
                elif nums[mid] > target:
                    right = mid - 1
                #else:  由于左侧区间没有保留右边界，所以不需要考虑死循环
                #   break
            return -1
        #特殊情况处理
        if not nums: return -1
        if len(nums) == 1 and nums[0] == target: return 0
        elif len(nums) == 1: return -1
        left, right = 0, len(nums) - 1
        if nums[right] > nums[left]: return bfind(left, right, target)
        else: rotate = bfind_rotate(left, right)
        #判断目标值在旋转前还是旋转后
        if target >= nums[0]: return bfind(0, rotate, target)
        return bfind(rotate + 1, right, target)

举例二（74. 搜索二维矩阵）
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

示例 1:
输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
输出: true
思路：本题先对于第一列使用二分查找寻找到目标值所在的行row,条件是target值大于当前行起始值，小于下一行起始值
然后对于row行进行第二次二分查找，寻找目标target.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
            if not matrix or not matrix[0]: return False	#特殊情况处理
            #对行应用二分查找，由于二分查找过程中会忽略最后一行，所以直接初始化row为最后一行
            row, bottom, top= len(matrix) - 1, 0, len(matrix) - 1
            while bottom <= top:
                mid = (bottom + top) // 2
                if matrix[mid][0] == target: return True
                elif mid < len(matrix) - 1 and matrix[mid][0] < target and matrix[mid + 1][0] > target:
                    row = mid
                    break
                elif matrix[mid][0] < target: bottom = mid + 1
                elif matrix[mid][0] > target: top = mid - 1
            #判断当row是最后一行时，是否符合题意
            if matrix[row][-1] < target : return False

			#对第row行进行二分查找
            left, right = 0, len(matrix[0]) - 1
            while left <= right:
                mid = (left + right) // 2
                if matrix[row][mid] == target:
                    return True
                if matrix[row][mid] < target:
                    left = mid + 1
                elif matrix[row][mid] > target:
                    right = mid - 1
            return False              

二、分治算法

介绍：在计算机科学中，分治法是构建基于多项分支递归的一种很重要的算法范式。字面上的解释是「分而治之」，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
这个技巧是很多高效算法的基础，如排序算法（快速排序、归并排序）、傅立叶变换（快速傅立叶变换）。

举例一 快速排序

class Solution {
    public int[] smallestK(int[] arr, int k) {
        helper1(0, arr.length - 1, arr);
        return Arrays.copyOf(arr, k);
    }
    public void quickSort(int start, int end, int[] nums){
    	//当排序数组长度小于等于1时直接中止排序
        if(start >= end) return;
        //在start处挖个坑， 保存起始位置
        int temp = nums[start], t0 = start, t1 = end;
        while(start < end){
        	//注：先向前遍历，当队尾的元素大于等于基准数据时,向前挪动high指针
        	//start > end 防止start越界end
            while(start < end && nums[end] >= temp) end--;
            //将队尾元素小于基准数据的值放到坑里，将坑变为end所在处
            swap(start, end, nums);
            //向后遍历，当队首的元素小于等于基准数据时，向后挪动start指针
            //start < end 防止start越界end
            while(start < end && nums[start] <= temp) start++;
            //将队首元素小于基准数据的值放到坑里，将坑变为start所在处
            swap(start, end, nums);
        }
        //对temp左右两侧继续排序
        quickSort(t0, start - 1, nums);
        quickSort(start + 1, t1, nums);
    }
    
    public void swap(int start, int end, int[] nums){
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
    }
}

class Solution {
public:
    void quicksort(vector<int>& arr, int start, int end) {
	    if (end - start < 1) return;
	    int tot1 = start, tot2 = end, tot = arr[start];
	    while (end > start)
	    {
		    while (end > start && arr[end] >= tot) end--;                     arr[start] = arr[end];
		    while (end > start && tot >= arr[start]) start++;                   arr[end] = arr[start];
	    }
	    arr[start] = tot;
	    quicksort(arr, tot1, start - 1);
	    quicksort(arr, start + 1, tot2);
    }
    vector<int> sortArray(vector<int>& nums) {
        quicksort(nums, 0, nums.size() - 1);
        return nums;
    }
    
};

举例二 漂亮数组
对于某些固定的 N，如果数组 A 是整数 1, 2, …, N 组成的排列，使得：
对于每个 i < j，都不存在 k 满足 i < k < j 使得 A[k] * 2 = A[i] + A[j]。
那么数组 A 是漂亮数组。
给定 N，返回任意漂亮数组 A（保证存在一个）。

示例 1：
输入：4
输出：[2,1,4,3]
思路:漂亮数组有以下性质：
（1）A是一个漂亮数组，如果对A中所有元素乘以一个常数，那么A还是一个漂亮数组。
（2）A是一个漂亮数组，如果删除一些A中所有元素，那么A还是一个漂亮数组。
（3）A是一个奇数构成的漂亮数组，B是一个偶数构成的漂亮数组，那么A+B也是一个漂亮数组
#我的做法，非分治
class Solution:
    def beautifulArray(self, N: int) -> List[int]:
        def DAC(memo):
            if len(memo) >= N: return memo
            left = [i * 2 - 1 for i in memo]
            right = [i * 2 for i in memo]
            memo = left + right
            return DAC(memo)
        memo = DAC([1])
        length = len(memo)
        for i in range(N, length):
            memo.remove(i + 1)
        return memo
        
#官方题解 上一种解法的性质依然继续沿用
class Solution:
    def beautifulArray(self, N):
        memo = {1: [1]}
        def f(N):
            if N not in memo:
            	#性质一
                odds = f((N+1)//2)	#奇数数组是由（N+1)/2个数字组成的漂亮数组放射而成
                evens = f(N//2)		#偶数数组是由	N/2个数字组成的漂亮数组放射而成
                #性质三
                memo[N] = [2*x-1 for x in odds] + [2*x for x in evens]
            return memo[N]
        return f(N)

第三题 归并排序
Given an array of integers nums, sort the array in ascending order.

class Solution {
    int[] arr;
    public int[] sortArray(int[] nums) {
        arr = nums;
        helper(0, nums.length - 1);
        return arr;
    }
	//分治算法
    public void helper(int start, int end){
        if(start >= end) return;
        int mid = (start + end) / 2;
        //将整体分为左右两个子区间进行排序
        helper(start, mid);
        helper(mid + 1, end);
        //合并子区间后重新排序
        insertSort(start, end);
    }
    public void insertSort(int start, int end){
        if(start >= end) return; //只有一个数字不需要排序
        int mid = (start + end) / 2; int i, j; //由归并排序可知待排数组左右两区间均完成排序
        //插入排序
        for(i = mid; i<=end; i++){
            int index = i - 1, temp = arr[i];
            //注意index >= start而不是0，用于规范排序区间 
            //注意arr[index] >= temp 而不是 arr[index] >= arr[i] 因为arr[i]会发生变化
            while(index >= start && arr[index] >= temp) {arr[index + 1] = arr[index]; index -= 1;}
            arr[index + 1] = temp;
        }
    }
}

最后

以上就是负责滑板为你收集整理的分治算法与二分查找的全部内容，希望文章能够帮你解决分治算法与二分查找所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。