算法（二）二分查找

文章目录

二分查找简介
实现方式
- 循环方式
- 递归方式
经典例子

二分查找简介

二分查找（binary search）算法，也叫折半算法。
二分查找是针对有序的数据集合的查找办法，如果是无序的数据结合就使用遍历。
二分查找之所以快速，是因为它再匹配不成功的时候，每次都能排除剩余元素中一半的元素，因此包含目标元素的有效范围就会收缩非常快。
时间复杂度： T(n) = O(logn)

实现方式

循环方式

package com.xxliao.algorithms.binary_search.demo;

/**
 * @author xxliao
 * @description: 在一个有序集合中，查找某数是否存在 -- 基础实现
 * @date 2024/5/30 0:40
 */
public class Demo01 {

    public static void main(String[] args) {
        //有序数组
        int[] nums = {3, 12, 24, 31, 46, 48, 52, 66, 69, 79, 82};
        System.out.println(binarySearch(nums,66));
        System.out.println(binarySearch(nums,55));
    }

    /**
     * @description  二分法基础实现
     * @author  xxliao
     * @date  2024/5/30 0:47
     */
    public static int binarySearch(int[] array,int destNum) {
        // 低索引
        int low = 0;
        // 高索引
        int high = array.length -1;
        // 中间索引
        int mid = 0;
        while(low<=high) {
            mid = (low + high) / 2;
            if(array[mid] == destNum) {
                return mid; //相等，找到该索引
            }else if(destNum < array[mid]){
                high = mid - 1; // 比中间值小，
            }else{
                low = mid + 1; // 比中间值大
            }
        }
        return -1;
    }
}

测试结果：
在这里插入图片描述

递归方式

package com.xxliao.algorithms.binary_search.demo;

/**
 * @author xxliao
 * @description: 在一个有序集合中，查找某数是否存在 -- 递归实现
 * @date 2024/5/30 0:40
 */
public class Demo02 {

    public static void main(String[] args) {
        //有序数组
        int[] nums = {3, 12, 24, 31, 46, 48, 52, 66, 69, 79, 82};
        System.out.println(binarySearch(nums,48));
        System.out.println(binarySearch(nums,55));
    }

    /**
     * @description  二分法 递归实现
     * @author  xxliao
     * @date  2024/5/30 0:47
     */
    public static int binarySearch(int[] array,int destNum) {
        // 低索引
        int low = 0;
        // 高索引
        int high = array.length -1;
        return binarySearch(array,low,high,destNum);
    }

    private static int binarySearch(int[] array,int low,int high,int destNum){
        //定义递归结束条件
        if(low > high)
            return -1;
        int mid = (low + high) / 2;
        if(array[mid] == destNum) {
            return mid; //相等，找到该索引
        }else if(destNum < array[mid]){
            high = mid - 1; // 比中间值小，
        }else{
            low = mid + 1; // 比中间值大
        }
        return binarySearch(array,low,high,destNum);
    }
}

测试结果：
在这里插入图片描述

经典例子

一个有序数组有一个数出现1次，其他数出现2次，找出出现一次的数
比如：1 1 2 2 3 3 4 4 5 5 6 6 7 出现1次的数是7。

使用二分查找： 1 有序、 2、时间复杂度 O(logn)。
偶数位索引跟后面的比相同，奇数位索引跟前面的比相同则说明前面的都对。
偶数位索引跟前面的比相同，奇数位索引跟后面的比相同则说明后面的都对。

package com.xxliao.algorithms.binary_search.demo;

/**
 * @author xxliao
 * @description:
 * 一个有序数组有一个数出现1次，其他数出现2次，找出出现一次的数
 * 比如：1 1 2 2 3 3 4 4 5 5 6 6 7 出现1次的数是7
 *
 * 使用二分查找： 1 有序、 2、时间复杂度 O(logn)
 * 偶数位索引跟后面的比相同，奇数位索引跟前面的比相同 则说明前面的都对
 * 偶数位索引跟前面的比相同，奇数位索引跟后面的比相同 则说明后面的都对
 *
 * @date 2024/5/30 1:06
 */

public class Demo03 {
    public static void main(String[] args) {
        int[] nums={1,2,2,3,3,4,4,5,5};
        //int[] nums = {1,1, 2, 2, 3, 4, 4, 5, 5,6,6,7,7};
        System.out.println(binarySearch(nums));
    }

    public static int binarySearch(int[] nums) {
        //低位索引
        int low = 0;
        //高位索引
        int high = nums.length - 1;
        //中间索引
        int mid = 0;
        while (low < high) {

            mid = (low + high) / 2;

            if (mid % 2 == 0) {//偶数位

                if (nums[mid] == nums[mid + 1]) {
                    // 与后面的数相等,前面的都对
                    low = mid + 1;
                } else if (nums[mid] == nums[mid - 1]) {
                    // 与前面的数相等,后面的都对
                    high = mid - 1;
                } else {// 就是这个数
                    return nums[mid];
                }
            } else {//奇数位

                if (nums[mid] == nums[mid - 1]) {
                    // 与前面的数相等,前面的都对
                    low = mid + 1;
                } else if (nums[mid] == nums[mid + 1]) {
                    //与后面的数相等,后面的都对
                    high = mid - 1;
                } else { // 就是这个数
                    return nums[mid];
                }
            }
        }
        //low=high
        return nums[low];
    }
}