二分查找\排序——分而治之☞二维数组中的查找

迈不过友情╰ 2024-04-07 15:41 51阅读 0赞

**目录**

一. 知识点：分治

二. 二分查找

三. 二维数组中的查找

--------------------

### **一. 知识点：分治** ###

> 分治即“分而治之”，“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子问题，子问题继续按照这样划分，直到问题可以被轻易解决；“治”指的是将子问题单独进行处理。经过分治后的子问题，需要将解进行合并才能得到原问题的解，因此整个分治过程经常用递归来实现。

--------------------

### 二. 二分查找 ###

题目：

> 给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1

**具体做法：**

>  *  step 1：从数组首尾开始，每次取中点值。
>  *  step 2：如果中间值等于目标即找到了，可返回下标，如果中点值大于目标，说明中点以后的都大于目标，因此目标在中点左半区间，如果中点值小于目标，则相反。
>  *  step 3：根据比较进入对应的区间，直到区间左右端相遇，意味着没有找到。

**python代码解：**

#
    # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    #
    # 
    # @param nums int整型一维数组 
    # @param target int整型 
    # @return int整型
    #
    class Solution:
        def search(self , nums: List[int], target: int) -> int:
            # write code here
            if len(nums)==0:
                return -1
            l = 0
            r = len(nums)-1
            while l<=r:
                m = int((l+r)/2)
                if nums[m] == target:
                    return m
                if nums[m] < target:
                    l = m+1
                else:
                    r = m-1
            return -1

**JavaScript代码解：**

/**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    function search( nums ,  target ) {
        // write code here
        if(nums.length===0) return -1
        let l = 0;
        let r = nums.length-1;
        while(l<=r){
            let m =((l+r)/2)>>>0
            if(nums[m]===target){
                return m
            }
            if(nums[m]<target){
                l = m+1
            }else{
                r = m-1
            }
        }
        return -1
    }
    module.exports = {
        search : search
    };

--------------------

### 三. 二维数组中的查找 ###

**问题描述：**

> 在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
> 
> \[
> 
> \[1,2,8,9\],  
> \[2,4,9,12\],  
> \[4,7,10,13\],  
> \[6,8,11,15\]
> 
> \]
> 
> 给定 target = 7，返回 true。
> 
> 给定 target = 3，返回 false。

**示例1**

> 输入：7,\[\[1,2,8,9\],\[2,4,9,12\],\[4,7,10,13\],\[6,8,11,15\]\]
> 
> 返回值：true
> 
> 说明：存在7，返回true

**思路：**

> 利用到矩阵内部的行列都是有序这个性质，我们再来找找规律：
> 
> 首先看四个角，左上与右下必定为最小值与最大值，而左下与右上就有规律了：**左下元素大于它上方的元素，小于它右方的元素，右上元素与之相反**。既然左下角元素有这么一种规律，相当于将要查找的部分分成了一个大区间和小区间，每次与左下角元素比较，我们就知道目标值应该在哪部分中，于是可以利用分治思维来做。

**具体做法：**

>  *  step 1：首先获取矩阵的两个边长，判断特殊情况。
>  *  step 2：首先以左下角为起点，若是它小于目标元素，则往右移动去找大的，若是他大于目标元素，则往上移动去找小的。
>  *  step 3：若是移动到了矩阵边界也没找到，说明矩阵中不存在目标值。

**python代码解：**

#
    # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    #
    # 
    # @param target int整型 
    # @param array int整型二维数组 
    # @return bool布尔型
    #
    class Solution:
        def Find(self , target: int, array: List[List[int]]) -> bool:
            # write code here
            if len(array) == 0:
                return False
            n = len(array)
            if len(array[0]) == 0:
                return False
            m = len(array[0])
            i = n-1
            j = 0
            while i>=0 and j<m:
                if array[i][j] < target:
                    j += 1
                elif array[i][j] > target:
                    i -= 1
                else:
                    return True
            return False

**JavaScript代码解：**

function Find(target, array)
    {
        // write code here
        if(array.length===0) return false
        let n = array.length
        if(array[0].length===0) return false
        let m = array[0].length
        let i = n-1
        let j = 0
        while(i>=0 && j<=m-1){
            if(array[i][j]>target){
                i--
            }else if(array[i][j]<target){
                j++
            }else{
                return true
            }
        }
        return false
    }
    module.exports = {
        Find : Find
    };