二分查找

1 二分查找

二分查找的时间复杂度：log2n

2 二分查找Java实现

    public static void main(String[] args) {
        // 这是我们要搜索的数组（必须是有序的）
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        // 我们要查找的目标值
        int target = 7;

        int result = binarySearch(arr, target);

        if (result == -1) {
            System.out.println("Element not present");
        } else {
            System.out.println("Element found at index: " + result);
        }
    }

private static int binarySearch(int[] arr, int target) {
        //定义左右指针
        int left = 0;
        int right = arr.length - 1;
        //循环条件：左指针<=右指针
        while (left <= right) {
            //定义一个temp指针 初始值为arr的一半
            int temp = left + (right - left) / 2;
            //判断temp元素是否等于target
            if (arr[temp] == target) {
                return temp;
            }
            //中间值 大于 目标值，目标值 中间值
            if (arr[temp] > target)
                //右指针左移
                right=temp-1;
            else
                left=temp+1;
        }
        //找不到就 -1
        return -1;
    }