二分搜索及其变形应用

xiaoxiao2021-02-28  6

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

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

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; } }

转载请注明原文地址: https://www.6miu.com/read-1100017.html

最新回复(0)