欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分搜索及其变形应用

程序员文章站 2022-07-12 09:43:11
...

    二分搜索(折半查找)是应用很广泛的一种算法,当出现有序序列时,我们可以立马想到能否可以用二分法,其写法也较为固定。我们可以把二分法视为分治的应用。但是如果不注意其变换条件也是很容易写错。下边给出了二分查找的非递归和递归写法,只要注意其边界判断和变换,代码很简单:

二分法的递归和非递归写法

package com.blog.binarysearch;

/**
 * @Description: 二分法(二分搜索 折半查找)  有序序列的搜索   时间复杂度为O(logn)
 * @Author: Jingzeng Wang
 * @Date: Created in 15:56  2017/7/23.
 */
public class BinarySearchDemo {

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 5, 7, 9, 11, 13};
        System.out.println(binarySearch(nums, 11));
        System.out.println(binarySearchRecursive(nums, 11, 0, nums.length - 1));
    }

    /**
     * 二分  非递归版本
     * <p>
     * right = num.length  left < right  right = mid;  另一种写法
     *
     * @param nums   已排序数组
     * @param keyNum 待查找数字
     * @return 返回查找的索引位置   没有则返回-1
     */
    public static int binarySearch(int[] nums, int keyNum) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            //int mid = start + (end - start) / 2; //直接平均可能溢出,可以用此算法
            int mid = (left + right) / 2;
            if (nums[mid] < keyNum) {
                left = mid + 1;
            } else if (nums[mid] > keyNum) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 二分搜索的递归写法
     *
     * @param nums
     * @param value
     * @param left
     * @param right
     * @return
     */
    public static int binarySearchRecursive(int[] nums, int value, int left, int right) {
        if (left > right)
            return -1;
        int mid = left + (right - left) / 2;
        if (nums[mid] < value)
            return binarySearchRecursive(nums, value, mid + 1, right);
        else if (nums[mid] > value)
            return binarySearchRecursive(nums, value, left, mid - 1);
        else return mid;
    }
}

二分法的变形应用

二分法的变形很多种,但是只要掌握了二分的核心思想,将转移条件写正确,基本就可以解决这些问题。比如一个有序序列中药查找的那个数出现很多次,求第一个出现的位置,求它最后出现的位置,求第一个小于某个数的数的位置,求第一个大于某个数的位置等等,只要出现有序序列,我们就可以思考此问题可否用二分法解决。下边给出一个题:统计一个数字在排序数组中出现的次数。
// hash表可以 遍历也可以 但是排序数组肯定有用  二分啊
// 二分的变形:找正好大于k的那个数的位置 与 正好小于k 的位置  然后相减   时间复杂度为 O(logn)
// 定位k第一次出现的位置 和 最后一次出现的位置

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if (array == null || array.length <= 0) {
            return 0;
        }
        int left = 0;
        int right = array.length - 1;
        int mid1 = (left + right) >> 1;
        // 找第一个k
        while (left <= right) {
            if (array[mid1] >= k) {
                right = mid1 - 1; 
            } else {
                left = mid1 + 1;  // < left 是始终指向小于k的  最后也是+1获得第一个k
            }
            
            mid1 = (left + right) >> 1;
        }
        mid1 = left;
        
        left = 0;
        right = array.length - 1;
        int mid2 = (left + right) >> 1;
        //找最后一个k
        while (left <= right) {
            if (array[mid2] > k) {
                right = mid2 - 1;   // 大于k的  获得最后一个k
            } else {
                left = mid2 + 1; 
            }
            
            mid2 = (left + right) >> 1;
        }
        mid2 = right;
        
        return mid2 - mid1 + 1;
    }
}