二分法检索

ha_lydms

发布于 2023-08-09 20:59:01

2770

文章被收录于专栏：学习内容学习内容

1、简介

二分法检索(binary search)又称折半检索，二分法检索的基本思想是设数组中的元素从小到大有序地存放在数组(array)中，首先将给定值key与数组中间位置上元素的关键码(key)比较， 如果相等：则检索成功;

若key小：则在数组前半部分中继续进行二分法检索；

若key大：则在数组后半部分中继续进行二分法检索。

这样，经过一次比较就缩小一半的检索区间，如此进行下去，直到检索成功或检索失败。

二分法检索是一种效率较高的检索方法。比如，我们要在数组[7, 8, 9, 10, 12, 20, 30, 40, 50, 80, 100]中查询到10元素，过程如下：

2、代码

 public class test07 {
    public static void main(String[] args) {
        int[]arr={30,20,50,10,80,9,7,12,199,23,44};
        int result = test07.myBinarySearch(arr, 20);
        System.out.println(result);
    }

    public static int myBinarySearch(int[]array,int value){
//        对数组进行排序
        Arrays.sort(array);
        System.out.println(Arrays.toString(array));
        int low=0;
        int hight=array.length-1;

        while (low<=hight){
            int mid=(low+hight)/2;
//            1、要找的值，正好等于中间的值；
            if (value==array[mid]){
                return mid;
            }
//            2、要找的值小于中间的值；
            if (value<array[mid]){
                hight=mid-1;
            }
//            3、要找的值大于中间的值；
            if (value>array[mid]){
                low=mid+1;
            }
        }
        return -1;
    }
}

3、打印的结果为：

4、方式二

package com.lydms.flink.test;

public class Test {

    public static void main(String[] args) {
        int value = 9;
        int[] ints = {1, 3, 5, 7, 9};

        int num = getNum(ints, value);
        System.out.println(num);


    }

    private static int getNum(int[] ints, int value) {
        int startNum = 0;
        int endNum = ints.length;

        while (startNum <= endNum) {
            int middleNum = (startNum + endNum) / 2;
            if (ints[middleNum] == value) {
                return middleNum;
            } else if (ints[middleNum] > value) {
                endNum = middleNum;
            } else {
                startNum = middleNum;
            }
        }
        return -1;
    }
}
```

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-12-08，如有侵权请联系 cloudcommunity@tencent.com 删除

int