数据结构 二分查找法

二分查找

• 二分查找概述：

查找指定元素在数组中的位置时，以前的方式是通过遍历，逐个获取每个元素，看是否是要查找的元素，这种方式当数组元素较多时，查找的效率很低。
二分法检索（binary search）又称折半检索，二分法检索的基本思想是设数组中的元素从小到大有序的存放在数组（array）中，首先将给定值 key 与数组中间位置上元素的关键码(key)比较，如果相等，则检索成功；
否则，若 key 小，则在数组前半部分中继续进行二分法检索;
若 key 大，则在数组后半部分中继续进行二分法检索。
这样，经过一次比较就缩小一半的检索区间，如此进行下去，直到检索成功或检索失败。

• 需求：

在数组{1,2,3,4,5,6,7,8,9,10}中,查找某个元素的位置

• 实现步骤：

1. 定义两个变量，表示要查找的范围。默认min = 0 ，max = 最大索引
2. 循环查找，但是min <= max
3. 计算出mid的值
4. 判断mid位置的元素是否为要查找的元素，如果是直接返回对应索引
5. 如果要查找的值在mid的左半边，那么min值不变，max = mid -1.继续下次循环查找
6. 如果要查找的值在mid的右半边，那么max值不变，min = mid + 1.继续下次循环查找
7. 当min > max 时，表示要查找的元素在数组中不存在，返回-1.

• 代码实现：

public class MyBinarySearchDemo {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int number = 11;

        //1.我现在要干嘛? --- 二分查找
        //2.我干这件事情需要什么? --- 数组 元素
        //3.我干完了,要不要把结果返回调用者 --- 把索引返回给调用者
        int index = binarySearchForIndex(arr, number);
        System.out.println(index);
    }

    private static int binarySearchForIndex(int[] arr, int number) {
        //1.定义查找的范围
        int min = 0;
        int max = arr.length - 1;
        //2.循环查找 min <= max
        while (min <= max) {
            //3.计算出中间位置 mid
            int mid = (min + max) >> 1;
            //mid指向的元素 > number
            if (arr[mid] > number) {
                //表示要查找的元素在左边.
                max = mid - 1;
            } else if (arr[mid] < number) {
                //mid指向的元素 < number
                //表示要查找的元素在右边.
                min = mid + 1;
            } else {
                //mid指向的元素 == number
                return mid;
            }
        }
        //如果min大于了max就表示元素不存在,返回-1.
        return -1;
    }
}

本文地址：https://blog.csdn.net/DruidZw/article/details/111027306