← 返回学习路线

SYSTEM

查找

Java基础查找system
src/content/notes/system/查找.md

查找

正常查找:从第一个元素开始遍历,一个一个的往后找,综合查找比较耗时

二分查找也称折半查找(Binary Search)是一种效率较高的查找方法,数组必须是有序数组

过程:每次先与中间的元素进行比较,如果大于往右边找,如果小于往左边找,如果等于就返回该元素索引位置,如果没有该元素,返回 -1

时间复杂度:O(logn)

/*定义一个方法,记录开始的索引位置和结束的索引位置。
取出中间索引位置的值,拿元素与中间位置的值进行比较,如果小于中间值,结束位置=中间索引-1.
取出中间索引位置的值,拿元素与中间位置的值进行比较,如果大于中间值,开始位置=中间索引+1.
循环正常执行的条件:开始位置索引<=结束位置索引。否则说明寻找完毕但是没有该元素值返回-1.*/
public class binarySearch {
    public static void main(String[] args) {
        int[] arr = {10, 14, 21, 38, 45, 47, 53, 81, 87, 99};
        System.out.println("81的索引是:" + binarySearch(arr,81));

    }

    public static int binarySearch(int[] arr, int des) {
        int start = 0;
        int end = arr.length - 1;

        // 确保不会出现重复查找,越界
        while (start <= end) {
            // 计算出中间索引值
            int mid = (start + end) / 2;
            if (des == arr[mid]) {
                return mid;
            } else if (des > arr[mid]) {
                start = mid + 1;
            } else if (des < arr[mid]) {
                end = mid - 1;
            }
        }
        // 如果上述循环执行完毕还没有返回索引,说明根本不存在该元素值,直接返回-1
        return -1;
    }
}

查找第一个匹配的元素:

public static int binarySearch(int[] arr, int des) {
        int start = 0;
        int end = arr.length - 1;

        while (start <= end) {
            int mid = (start + end) / 2;
            if (des == arr[mid]) {
                //如果 mid 等于 0,那这个元素已经是数组的第一个元素,那肯定是我要找的
                if (mid == 0 || a[mid - 1] != des) {
                    return mid;
                } else {
                    //a[mid]前面的一个元素 a[mid-1]也等于 value,
                    //要找的元素肯定出现在[low, mid-1]之间
                    high = mid - 1
                }
            } else if (des > arr[mid]) {
                start = mid + 1;
            } else if (des < arr[mid]) {
                end = mid - 1;
            }
        }
        return -1;
    }