二分查找算法及拓展

小咪咪 2023-02-20 03:13 56阅读 0赞

**目录**

一、概念及分析

二、二分查找实现（Java）

三、进阶例题

3.1 题目描述

3.2 题目分析

3.3 题目解答

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

# 一、概念及分析 #

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，**折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列**。比如 序列 1、5、13、15、17。

时间复杂度 O(logn)     空间复杂度O（n）

时间复杂度分析：

二分查找的基本思想是将n个元素分成大致相等的两部分，取a\[n/2\]与x做比较，如果x=a\[n/2\],则找到x,算法中止；如果x<a\[n/2\],则只要在数组a的左半部分继续搜索x,如果x>a\[n/2\],则只要在数组a的右半部搜索x.

时间复杂度即是while循环的次数。

总共有n个元素，

渐渐跟下去就是n,n/2,n/4,....n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数

由于你n/2^k取整后>=1

即令n/2^k=1

可得k=log2n,（是以2为底，n的对数）

所以时间复杂度可以表示为O(log2n)

空间复杂度分析：

因为全程查找只在原数组空间内进行，所以空间复杂度O（n）

# 二、二分查找实现（Java） #

public class halfSearch {
    
            public static int halfSearch(int A[],int key) {
                int len = A.length;
                int left = 0, right = len - 1, mid;
                while (left <= right) {
                    mid = (left + right) / 2;
                    if (A[mid] == key) return mid;
                    else if (A[mid] > key) {
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                }
                return -1;
            }
            public static void main(String[] args) {
                int A[]={1,3,5,13,17,19};
                System.out.println(halfSearch(A,5));
            }
    }

# 三、进阶例题 #

## 3.1 题目描述 ##

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 \[0,1,2,4,5,6,7\] 可能变为 \[4,5,6,7,0,1,2\] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

**你的算法时间复杂度必须是 O(log n) 级别。**

示例 1:

输入: nums = \[4,5,6,7,0,1,2\], target = 0  
输出: 4  
示例 2:

输入: nums = \[4,5,6,7,0,1,2\], target = 3  
输出: -1

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 3.2 题目分析 ##

这是一个时间复杂度要求为O(logn)的查找算法，首先想到二分查找算法。但是二分查找算法的基本前提是**有序线性表，**这里显然不能直接使用**。二分查找的原理即是利用元素有序关系将待查找元素定位到以mid为界限的两个集合中。所以如果我们可以用已知条件将待查元素定位到两个以mid为界限的集合中，同样是实现了二分查找，时间复杂度同样为O(logn)。**接下来就是如何划分以mid为界限的集合了。因为只是旋转数组，所以必定有超过一半元素是有序的，抓住这一半元素有序的特点，可以大做文章：假设nums\[0\]~\[mid\]有序，若target的值在nums\[0\]~\[mid\]之间，可以定位在左半部分，否则定位在右半部分。

## 3.3 题目解答 ##

图解：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvbmdodTE0NTg3MDA3_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvbmdodTE0NTg3MDA3_size_16_color_FFFFFF_t_70 1][]

代码实现（Java）：

class Solution {
        public int search(int[] nums, int target) {
            int len=nums.length;
            int left=0,right=len-1,mid;
            while(left<=right){
                mid=left+(right-left)/2;
                if(target==nums[mid])return mid;
                if(nums[mid]>nums[right]){//判断前一部分有序，对应情况一
                    if(target>=nums[left]&&target<nums[mid]){
                        right=mid-1;
                    }else{
                        left=mid+1;
                    }
                }else{ //后一部分有序，对应情况二/三
                    if(target>nums[mid]&&target<=nums[right]){
                        left=mid+1;
                    }else{
                        right=mid-1;
                    }
                }
            }
            return -1;
        }
    }

## 3.4 [剑指 Offer 11. 旋转数组的最小数字][Offer 11.] ##

难度简单99收藏分享切换为英文关注反馈

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 `[3,4,5,1,2]` 为 `[1,2,3,4,5]` 的一个旋转，该数组的最小值为1。

**示例 1：**

输入：[3,4,5,1,2]
    输出：1

**示例 2：**

输入：[2,2,2,0,1]
    输出：0

class Solution {
        public int minArray(int[] numbers) {
            int left=0;
            int right=numbers.length-1;
            while(left<right){ //逼近式
                int mid=left+(right-left)/2;
                if(numbers[mid]>numbers[right]){
                    left=mid+1;
                }else if(numbers[mid]<numbers[right]){
                    right=mid;
                }else{
                    right--;//[2,2,2,1,2,2,2]把右边重复2删除
                }
            }
            return numbers[left];
        }
    }

## [410. 分割数组的最大值][410.] ##

给定一个非负整数数组和一个整数 *m*，你需要将这个数组分成 *m *个非空的连续子数组。设计一个算法使得这 *m *个子数组各自和的最大值最小。

**注意:**  
数组长度 *n *满足以下条件:

*  1 ≤ *n* ≤ 1000
 *  1 ≤ *m* ≤ min(50, *n*)

**示例:**

输入:
    nums = [7,2,5,10,8]
    m = 2
    
    输出:
    18
    
    解释:
    一共有四种方法将nums分割为2个子数组。
    其中最好的方式是将其分为[7,2,5] 和 [10,8]，
    因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

class Solution {
        public int splitArray(int[] nums, int m) {
            int left=0,right=0;
            for(int i:nums){
                left=(i>left)?i:left;
                right+=i;
            }
            //System.out.println("left:"+left+" right:"+right);
            while(left<right){ //逼近式
            // 如果 cnt>m，说明划分的子数组多了，即我们找到的 mid 偏小，故 l=mid+1l=mid+1；否则，说明划分的子数组少了，即 mid 偏大(或者正好就是目标值),即h=midh=mid。
                int mid=left+(right-left)/2;
                int sum=0;
                int count=1;
                for(int i:nums){
                    sum+=i;
                    if(sum>mid){
                        sum=i;
                        count++;
                    }
                }
                if(count>m){//count数偏大，结果值偏小，left右移
                    left=mid+1;
                }else{
                    right=mid;
                }
            }
            return left;
        }
    }

# 四、进阶例题2 #

## 4.1 题目描述 ##

[378. 有序矩阵中第K小的元素][378. _K]

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。  
请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

示例：

matrix = \[  
   \[ 1,  5,  9\],  
   \[10, 11, 13\],  
   \[12, 13, 15\]  
\],  
k = 8,

返回 13。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 4.2 题目分析与解答 ##

class Solution {
        public int kthSmallest(int[][] matrix, int k) {
            int n = matrix.length;
            int left = matrix[0][0];
            int right = matrix[n - 1][n - 1];
            while (left < right) {
                int mid = left + ((right - left) >> 1);
                if (check(matrix, mid, k, n)) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        }
    
        public boolean check(int[][] matrix, int mid, int k, int n) {
            int i = n - 1;
            int j = 0;
            int num = 0;
            while (i >= 0 && j < n) {
                if (matrix[i][j] <= mid) {
                    num += i + 1;
                    j++;
                } else {
                    i--;
                }
            }
            return num >= k;
        }
    }
    /*关于二分查找法中 kthSmallest(int[][] matrix, int k) 返回值为 left 的解释：其实返回left和right都对，因为最后跳出循环 while (left < right) 时 left=right。( left 和 right的作用就是无限逼近，直到逼出最后结果值。而 left=mid+1决定了left不可能突然增加到大于 right值，最多也就等于 right值，当left=right时，不就正好逼出结果值了吗，结果值=left=right。）*/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvbmdodTE0NTg3MDA3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020072215151974.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvbmdodTE0NTg3MDA3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvbmdodTE0NTg3MDA3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200622230155953.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvbmdodTE0NTg3MDA3,size_16,color_FFFFFF,t_70
[Offer 11.]: https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/
[410.]: https://leetcode-cn.com/problems/split-array-largest-sum/
[378. _K]: https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/