欢迎光临
我们一起进阶

Java 数组(四):二分查找

扫码或搜索:沉默王二
发送 290992
即可立即永久解锁本站全部文章

二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。 但是,折半查找要求数组必须采用顺序存储结构,而且数组中元素按关键字有序排列。

案例

  1. 查找第一个值等于给定值的元素下标
package com.silence.arts.leetcode.binary;

/**
 * <br>
 * <b>Function:</b><br>
 * <b>Author:</b>@author Silence<br>
 * <b>Date:</b>2018-10-29 22:53<br>
 * <b>Desc:</b>二分查找变形题目<br>
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] a = {1, 3, 4, 5, 6, 8, 8, 8, 11, 18};
        System.out.println(bsearch4(a, a.length, 12));
    }

    /**
     * 变形一:二分查找变形题,查找第一个值等于给定值的元素下标
     * int[] a = {1, 3, 4, 5, 6, 8, 8, 8, 11, 18};
     * 如查找8,应该返回5
     *
     * @param array
     * @param n
     * @param value
     * @return
     */
    private static int bsearch1(int[] array, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (array[mid] > value) {
                high = mid - 1;
            } else if (array[mid] < value) {
                low = mid + 1;
            } else {
                if (mid == 0 || array[mid - 1] != value) {
                    return mid;
                } else {
                    high = mid - 1;
                }
            }
        }
        return -1;
    }

这里查找第一个值等于给定值的元素下标,二分经常是用来查找给定值的下标,但是当有很多相同值的时候,这个算法就是查询第一个值的。

  1. 查找最后一个值等于给定值的元素
/**
     * 变形二:查找最后一个值等于给定值的元素
     *
     * @param array
     * @param n
     * @param value
     * @return
     */
    private static int bsearch2(int[] array, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (array[mid] > value) {
                high = mid - 1;
            } else if (array[mid] < value) {
                low = mid + 1;
            } else {
                if (mid == n - 1 || array[mid + 1] != value) {
                    return mid;
                } else {
                    low = mid + 1;
                }
            }
        }
        return -1;
    }

这里查找最后一个值等于给定值的元素,跟上边一个类似,这里是查询最后一个。

  1. 查找第一个大于等于给定值的元素
 /**
     * 变形三:查找第一个大于等于给定值的元素
     *
     * @param array
     * @param n
     * @param value
     * @return
     */
    private static int bsearch3(int[] array, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (array[mid] >= value) {
                if ((mid == 0) || (array[mid - 1] < value)) {
                    return mid;
                } else {
                    high = mid - 1;
                }
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }
  1. 查找最后一个小于等于给定值的元素
/**
     * 变形四:查找最后一个小于等于给定值的元素
     * int[] a = {1, 3, 4, 5, 6, 8, 8, 8, 11, 18};
     * 如value = 12,则应该返回11的下标8
     * System.out.println(bsearch4(a, a.length, 12));
     *
     * @param array
     * @param n
     * @param value
     * @return
     */
    private static int bsearch4(int[] array, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (array[mid] > value) {
                high = mid - 1;
            } else {
                if (mid == n - 1 || array[mid + 1] > value) {
                    return mid;
                } else {
                    low = mid + 1;
                }
            }
        }
        return -1;
    }
}

赞(0) 打赏
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

小白学堂,学的不止是技术,更是前程

关于我们免责声明

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏