二分查找及其变形问题

二分查找及其变形问题

文章目录

• 二分查找
• • 概述
  • 算法分析
  • 二分查找及其变形问题Java实现
• 旋转数组的二分查找
• • 概述
  • Java实现

二分查找 概述

• 要使用二分查找，给的数据需要具备两个基本的特性：
  1. 数据是有序的。
  2. 数据支持随机访问。

算法分析

• 二分查找的时间复杂度是 O(logn)，空间复杂度是 O(1)

二分查找及其变形问题Java实现

public class BinarySearch {
    public static void main(String[] args) {
        int[] array = new int[]{1, 3, 5, 7, 9, 11, 19};
//        System.out.println(binarySearch(array, 19));
//        System.out.println(binarySearchGE(array, 10));
        System.out.println(binarySearchLE(array, 8));
    }

    public static int binarySearch(int[] arr, int k) {
        int f = 0, b = arr.length - 1, mid;
        while (f <= b) {
            mid = f + (b - f) / 2;//这样计算可以防止数据溢出
            if (k == arr[mid]) return mid;
            if (k < arr[mid]) b = mid - 1;
            else if (k > arr[mid]) f = mid + 1;
        }
        return -1;
    }

    
    public static int binarySearchGE(int[] arr, int target){
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
//            System.out.println(left + " " + mid + " " + right);
            if (target > arr[mid]) left = mid + 1;//如果是查第一个>目标值的数，只需要改成target >= arr[mid]
            else right = mid - 1;
        }
        return left;
    }

    
    public static int binarySearchLE(int[] arr, int target){
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
//            System.out.println(left + " " + mid + " " + right);
            if (target < arr[mid]) right = mid - 1;//如果是查第一个<目标值的数，只需要改成target <= arr[mid]
            else left = mid + 1;
        }
        return right;
    }
}

• 计算mid时注意数据溢出问题：例如，我们知道 int 整数的最大值大概是 2^31 - 1 大概为 21 亿。而 left 和 right 这两个数相加是有可能超过 21 亿的，例如 left = 12亿，right = 13 亿。这个时候，两个数的和超过了最大值，就会产生溢出了。

旋转数组的二分查找 概述

• 参考：https://blog.csdn.net/WantFlyDaCheng/article/details/100078712

Java实现

public class RotatedBinarySearch {
    public static void main(String[] args) {
        int[] array = new int[]{1, 3, 5, 7, 9, 11, 19};
        System.out.println(rotatedBinarySearch(array, 19));
    }

    public static int rotatedBinarySearch(int[] arr, int target){
        // 最左侧元素下标
        int left = 0;
        // 最右侧元素下标
        int right = arr.length - 1;
        while(left <= right){
            // 中间元素下标
            int mid = left + (right - left) / 2;
            if(arr[mid] == target) return mid;
            // 情况1：如果中间元素在旋转点左侧
            if(arr[mid] >= arr[left]){
                //target 如果位于中间元素的左侧
                if(arr[mid] > target && target >= arr[left]) right = mid - 1;
                else left = mid + 1;
            }
            // 情况2：中间元素在旋转点的右侧
            else{
                // target 如果位于中间元素的右侧
                if(arr[mid] < target && target <= arr[right]) left = mid + 1;
                else right = mid - 1;
            }
        }
        return -1;
    }
}