Java 二分查找算法题目练习 | 极客日志

Javajava算法

Java 二分查找算法题目练习

Java 二分查找算法题目练习涵盖了多个经典 LeetCode 问题，包括基础二分查找、查找元素范围、平方根计算、插入位置、山脉数组峰值、旋转数组最小值及缺失数字查找。文章通过暴力解法对比引出二分算法原理，重点讲解了利用二段性将时间复杂度优化至 O(log N) 的核心思想。提供了多种解题思路如哈希、遍历、求和、位运算及二分查找的具体 Java 代码实现，并分析了时间与空间复杂度，适合希望巩固二分搜索技巧的开发者阅读。

PentesterX发布于 2026/2/80 浏览

Java 二分查找算法题目练习

二分查找

二分查找

题目解析：在一个有序数组中找一个 target，找到返回其下标，找不到返回 -1 算法原理：1. 暴力解法：遍历整个数组进行查找时间复杂度 O(N)；2. 朴素二分算法：我们可以发现其数组是可以根据一个值将其分为两部分并且可以比较然后舍弃一部分，此时这个数组具有'二段性'，因此可以使用二分算法。

class Solution {
    public int search(int[] nums, int target) {
        // 此时就用 left 和 right 两个变量在左右两边
        // 使用 mid 来表示其中间的下标，因为其有序
        // 这样我们每次比较一次其就会干掉一半的数这个效率是很高的
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2; // 防溢出
            if (target > nums[mid]) {
                // 在 [mid+1 , right]
                left = mid + 1;
            } else if (target < nums[mid]) {
                // 在 [left,mid - 1]
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

时间复杂度：O(log N) 空间复杂度：O(1)

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

极客日志微信公众号二维码

更多推荐文章

相关免费在线工具

Keycode 信息
查找任何按下的键的javascript键代码、代码、位置和修饰符。在线工具，Keycode 信息在线工具，online
Escape 与 Native 编解码
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。在线工具，Escape 与 Native 编解码在线工具，online
JavaScript / HTML 格式化
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。在线工具，JavaScript / HTML 格式化在线工具，online
JavaScript 压缩与混淆
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。在线工具，JavaScript 压缩与混淆在线工具，online
加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ret = new int[2];
        ret[0] = ret[1] = -1;
        if (nums.length == 0) {
            return ret;
        }
        int left = 0;
        int right = nums.length - 1;
        // 先左边二分
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        // 此时 left 与 right 相遇就会结束
        if (nums[left] != target) {
            return ret;
        }
        // 反之就找到了左端点
        ret[0] = left;
        left = 0;
        // 可以不用重置，因此此时上面 left 对应就是其开始位置
        right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        ret[1] = right;
        return ret;
    }
}

class Solution {
    public int mySqrt(int x) {
        // 此时如果 x<1，此时只保留整数，就是 0
        if (x < 1) {
            return 0;
        }
        // 防止数据超出 long
        long left = 1;
        long right = x;
        while (left < right) {
            long mid = left + (right - left + 1) / 2;
            if (mid * mid <= x) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return (int) left;
    }
}

class Solution {
    public int searchInsert(int[] nums, int target) {
        // 使用二分算法
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        // 注意此时可能从头到尾都是< target
        return nums[right] < target ? right + 1 : right;
    }
}

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        // 因为其山脉我们呢可以分为两部分
        // 峰值左边是递增的
        // 峰值右边是递减的
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (arr[mid - 1] < arr[mid]) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

class Solution {
    public int findMin(int[] nums) {
        int right = nums.length - 1;
        int n = right;
        int left = 0;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[n]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
}

// 哈希
class Solution {
    public int takeAttendance(int[] records) {
        // 使用 hashSet<Integer> set = new HashSet<>();
        for (int record : records) {
            // set.add(record);
        }
        // 先全部将其放入 hash 中，让后一个一个判断其是否在其中就行
        int len = records.length;
        for (int i = 0; i < len; i++) {
            // if (!set.contains(i)) {
            //     return i;
            // }
        }
        // 缺少最后一个
        return len;
    }
}

// 直接遍历
class Solution {
    public int takeAttendance(int[] records) {
        // 直接遍历
        for (int i = 0; i < records.length; i++) {
            if (records[i] != i) {
                return i;
            }
        }
        return records.length;
    }
}

// 求和
class Solution {
    public int takeAttendance(int[] records) {
        // 使用求和方式也可以
        int len = records.length;
        int sum = len * (len + 1) / 2;
        for (int i = 0; i < len; i++) {
            sum -= records[i];
        }
        return sum;
    }
}

// 位运算
class Solution {
    public int takeAttendance(int[] records) {
        // 使用位运算符^
        int ret = 0;
        for (int i = 0; i < records.length; i++) {
            ret ^= records[i] ^ i;
            // 此时最后一个下标没有异或
        }
        return ret ^ records.length;
    }
}

// 二分算法
class Solution {
    public int takeAttendance(int[] records) {
        // 此时就可以将其数字分为两个部分
        // 一部分是其值和下标一样
        // 另一部分是不一样
        int left = 0;
        int right = records.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (records[mid] == mid) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return records[left] == left ? left + 1 : left;
    }
}