Java二分算法題目練習(xí)實戰(zhàn)教程

更新時間：2025年11月04日 11:56:04 作者：代碼不停

二分查找(Binary?Search)是一種非常高效的查找算法,它在有序數(shù)組或有序列表中通過反復(fù)將搜索范圍分為兩半來查找目標(biāo)元素,這篇文章主要介紹了Java二分算法題目練習(xí)的相關(guān)資料,需要的朋友可以參考下

二分查找

https://leetcode.cn/problems/binary-search/

題目解析：在一個有序數(shù)組中找一個target ，找到返回其下標(biāo)，找不到返回-1
算法原理：1.暴力解法：遍歷整個數(shù)組進行查找時間復(fù)雜度O(N)
2.樸素二分算法：我們可以發(fā)現(xiàn)其數(shù)組是可以根據(jù)一個值將其分為兩部分并且可以比較然后舍棄一部分，此時這個數(shù)組具有“二段性”，因此可以使用二分算法

class Solution {
    public int search(int[] nums, int target) {
        //此時就用left和right兩個變量在左右兩邊
        //使用mid來表示其中間的下標(biāo)，因為其有序
        //這樣我們每次比較一次其就會干掉一半的數(shù)這個效率是很高的
        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;
    }
}

時間復(fù)雜度：O(log N )
空間復(fù)雜度：O(1)

在排序數(shù)組中查找元素的第一個和最后一個位置

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/

題目解析：就是給了我們一個target，讓我們在一個非遞減的數(shù)組中找其開始和結(jié)束下標(biāo)，并返回，如果找不到就返回[-1,-1]
解法一：暴力解法，時間復(fù)雜度O(N)
解法二：樸素二分查找，由于我們不確定找的數(shù)是其開始和結(jié)束位置，因此有可能全部遍歷，因此時間復(fù)雜度是O(N)
解法三：左右二分算法

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相遇就會結(jié)束
        if(nums[left] != target){
            return ret;
        }
        //反之就找到了左端點
        ret[0] = left;

        left = 0;//可以不用重置，因此此時上面left對應(yīng)就是其開始位置
        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;
    }
}

x的平方根

https://leetcode.cn/problems/jJ0w9p/description/

class Solution {
    public int mySqrt(int x) {
        //此時如果x<1，此時只保留整數(shù)，就是0
        if(x < 1){
            return 0;
        }
        //防止數(shù)據(jù)超出
        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;
    }
}

搜索插入位置

https://leetcode.cn/problems/search-insert-position/description/

題目解析：在一個無重復(fù)元素的升序數(shù)組中找出其目標(biāo)值的位置，但是可能不存在，不存在的話就返回其按順序插入的位置
二分算法：因為其可以將其數(shù)組分為>= target和<target的兩部分，并且可以舍棄<target這個部分，因此使用二分算法，并且還是當(dāng)left 等于 right結(jié)束

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;
    }
}

山脈數(shù)組的峰頂索引

https://leetcode.cn/problems/peak-index-in-a-mountain-array/description/

題目解析：在一個一邊遞增，另一邊遞減的數(shù)組中找出其最大值
因此只需要找出其遞增和遞減中間的值下標(biāo)就可以

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;
    }
}

尋找峰值

https://leetcode.cn/problems/find-peak-element/description/

題目解析：在一個數(shù)組中，找其峰值，并且可能有多個，只需返回任意一個就行
二分算法：因為其是必然有峰值的，并且是不存在兩個元素相同，因此其會出現(xiàn)兩種情況，要么是遞增，要么遞減，因此按照分類使用二分算法

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;
    }
}

尋找旋轉(zhuǎn)排序數(shù)組中的最小值

https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/

題目解析：原本一個自增的數(shù)組，經(jīng)過旋轉(zhuǎn)，讓我們找出其最小的值
算法原理：暴力解法：直接遍歷找最小值
二分算法：我們可以以最后一個下標(biāo)的值為基準(zhǔn)值，因此數(shù)組可以分為兩個部分，一半是>nums[n-1]，一半是 <= nums[n - 1]，就這樣根據(jù)二段性就可以使用二分算法\

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];
    }
}

點名

https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/description/

題目解析：就是一個遞增的數(shù)組，并且其下標(biāo)和其對應(yīng)的值是對應(yīng)的，中間缺了一個數(shù)導(dǎo)致其不對應(yīng)了，我們要找到這個數(shù)

//哈希
class Solution {
    public int takeAttendance(int[] records) {
        //使用hash
        Set<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;
            //此時最后一個下標(biāo)沒有異或
        }
        return ret^records.length;
    }
}

//二分算法
class Solution {
    public int takeAttendance(int[] records) {
        //此時就可以將其數(shù)字分為兩個部分
        //一部分是其值和下標(biāo)一樣
        //另一部分是不一樣
        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;
    }
}