Java實現二分法變種的示例代碼

更新時間：2024年04月30日 10:11:59 作者：一葉浮萍歸大海

這篇文章主要為大家介紹了Java實現二分法變種的示例代碼復,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪

一、引言

二分法，又稱二分查找、折半查找，是一種在有序數組中查找某一特定元素的搜索算法。其核心思想是通過將目標數據與有序的數據序列進行比較，每次查找都將數據序列一分為二，確定目標數據在哪一半中，直到找到目標數據或者確定目標數據不存在。二分法的時間復雜度為O(log n)，相比于順序查找的O(n)，效率更高。然而，在實際應用中，我們可能會遇到一些特殊情況，需要對二分法進行一定的變種以滿足特定的需求。本文將介紹幾種常見的二分法變種，并給出Java實現。

二、二分法變種

查找第一個等于給定值的元素

在某些情況下，我們不僅需要判斷數組中是否存在某個元素，還需要找到該元素在數組中的第一個位置。這可以通過在二分查找的基礎上稍作修改來實現。當找到目標元素時，我們并不立即返回，而是繼續(xù)向左查找，直到找到第一個等于目標值的元素。

Java實現如下：

public int findFirstEqual(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) {
            right = mid - 1; // 繼續(xù)向左查找
        } else {
            left = mid + 1;
        }
    }
    // 檢查left是否越界以及nums[left]是否等于target
    if (left >= 0 && nums[left] == target) {
        return left;
    } else {
        return -1; // 未找到
    }
}

查找最后一個等于給定值的元素

與查找第一個等于給定值的元素類似，我們也可以通過修改二分查找算法來找到最后一個等于給定值的元素。當找到目標元素時，我們并不立即返回，而是繼續(xù)向右查找，直到找到最后一個等于目標值的元素。

Java實現如下：

public int findLastEqual(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1; // 繼續(xù)向右查找
        }
    }
    // 檢查right是否越界以及nums[right]是否等于target
    if (right >= 0 && nums[right] == target) {
        return right;
    } else {
        return -1; // 未找到
    }
}

查找插入位置

在某些情況下，我們需要在有序數組中插入一個元素，并返回插入后的索引。如果數組中已存在該元素，則返回該元素的索引；否則，返回應該插入的位置。這同樣可以通過修改二分查找算法來實現。

Java實現如下：

public int searchInsert(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid; // 找到目標元素，返回其索引
        } else if (nums[mid] < target) {
            left = mid + 1; // 目標元素在右半部分
        } else {
            right = mid - 1; // 目標元素在左半部分或不存在（此時right指向的位置應插入target）
        }
    }
    // 未找到目標元素，返回應插入的位置
    return left;
}