526互联

java与算法基础（二） 二分查找

发布时间 2023-12-25 20:07:21作者: 一个衰仔

二分查找基本算法

用于查找已排列数组，且一般没有重复数

左闭右开

查找区间为 [ Left , Right ) ,比较Left和Right中间的那个数和Target的。如果中间数大于target,将Left设为Middle-1;如果中间数小于target,将Right设为Middle。

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length;//因为是左开右闭，[Left,Right)
        while (left < right) {// 因为left == right的时候，在[left, right)是无效的空间
            int mid = left + ((right - left) / 2);
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid;
        }
        return -1;
    }
}

左闭右闭

查找区间为 [ Left , Right ] ,比较Left和Right中间的那个数和Target的。如果中间数大于target,将Left设为Middle-1;如果中间数小于target,将Right设为Middle+1。

 public int search(int[] nums, int target) {
        int Left = 0; // 左初始化为最左边一格
        int Right = nums.length - 1; // 左初始化为最右边一格

        // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
        if (target < nums[Left] || target > nums[Right])
            return -1;
        while (Left <= Right) {
            int Middle = Left + (Right - Left) / 2;
            if (nums[Middle] < target)
                Left = Middle + 1;
            else if (nums[Middle] > target)
                Right = Middle - 1;
            else
                return Middle;
        }
        return -1;
    }

此外，观察到如果target不在数组里。循环结束后，Left是比这个数大的数里最小的，Right是比这个数小的数里最大的

在排序数组中查找元素的第一个和最后一个位置

题目：

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。

可以通过两次二分查找（左闭右闭），分别查找左边界和有边界。先设左右边界为-1，若寻找到target再赋其他值。左边界既先找到等于目标的数并假令左边界为这个数，再令Right=Middle-1 继续寻找左边是否依然有等于target的数。右边界寻找同理。

 public int[] searchRange(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int LeftSearch = -1;
        int RightSearch = -1;
        // 计算左边界（既：二分查找找到最左边的等于target的数）
        while (left <= right) {
            int midle = left + (right - left) / 2;
            if (nums[midle] < target) {
                left = midle + 1;
            } else if (nums[midle] > target) {
                right = midle - 1;
            } else if (nums[midle] == target) {
                /* 若匹配到target，先假令第一个数等于middle
                再查找左半边有没有依然等于target的 */
                LeftSearch = midle;
                right = midle - 1;
            }
        }
        //
        left = 0;
        right = nums.length - 1;
        // 计算右边界（既：二分查找找到最右边的等于target的数）
        while (left <= right) {
            int midle = left + (right - left) / 2;
            if (nums[midle] < target) {
                left = midle + 1;
            } else if (nums[midle] > target) {
                right = midle - 1;
            } else if (nums[midle] == target) {
            /*若匹配到target，先假令最后一个数等于middle
                再查找右半边有没有依然等于target的*/  
                RightSearch = midle;
                left = midle + 1;
            }
        }

        return new int[] { LeftSearch, RightSearch };
    }