Comment implémenter la dichotomie en Java

Dans un tableau ordonné, déterminez si un certain nombre existe

Idée :

• Puisqu'il s'agit d'un tableau ordonné, vous pouvez d'abord obtenir la position médiane, et le point médian peut diviser le tableau en gauche et les moitiés droites.

• Si la valeur de la position médiane est égale à la valeur cible, renvoyez directement la position médiane.

• Si la valeur de la position médiane est inférieure à la valeur cible, allez sur le côté gauche du point médian du tableau et recherchez de la même manière.

• Si la valeur de la position médiane est supérieure à la valeur cible, prenez le côté droit du point médian du tableau et recherchez de la même manière.

• Si vous n'êtes pas trouvé au final, retournez : -1.

Code

class Solution {
    public int search(int[] arr, int t) {
        if (arr == null || arr.length < 1) {
            return -1;
        }
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int m = l + ((r - l) >> 1);
            if (arr[m] == t) {
                return m;
            } else if (arr[m] > t) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return -1;
    }
}

Complexité temporelle O(logN). O(logN)。

在一个有序数组中，找大于等于某个数最左侧的位置

示例 1:

输入: nums = [1,3,5,6], target = 5

输出: 2

说明：如果要在num这个数组中插入 5 这个元素，应该是插入在元素 3 和 元素 5 之间的位置，即 2 号位置。

示例 2:

输入: nums = [1,3,5,6], target = 2

输出: 1

说明：如果要在num这个数组中插入 2 这个元素，应该是插入在元素 1 和 元素 3 之间的位置，即 1 号位置。

示例 3:

输入: nums = [1,3,5,6], target = 7

输出: 4

说明：如果要在num这个数组中插入 7 这个元素，应该是插入在数组末尾，即 4 号位置。

通过上述示例可以知道，这题本质上就是求在一个有序数组中，找大于等于某个数最左侧的位置，如果不存在，就返回数组长度（表示插入在最末尾位置）

我们只需要在上例基础上进行简单改动即可，上例中，我们找到满足条件的位置就直接return了

if (arr[m] == t) {
    return m;
}

在本问题中，因为要找到最左侧的位置，所以，在遇到相等的时候，只需要先把位置记录下来，不用直接返回，然后继续去左侧找是否还有满足条件的更左边的位置。

同时，在遇到arr[m] > t条件下，也需要记录下此时的m位置，因为这也可能是满足条件的位置。

代码：

class Solution {
    public static int searchInsert(int[] arr, int t) {
        int ans = arr.length;
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int m = l + ((r - l)>>1);
            if (arr[m] >= t) {
                ans = m;
                r = m - 1;
            } else  {
                l = m + 1;
            } 
        }
        return ans;
    }
}

整个算法的时间复杂度是O(logN)。

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

思路

本题也是用二分来解，当通过二分找到某个元素的时候，不急着返回，而是继续往左（右）找，看能否找到更左（右）位置匹配的值。

代码如下：

class Solution {
    public static int[] searchRange(int[] arr, int t) {
        if (arr == null || arr.length < 1) {
            return new int[]{-1, -1};
        }
        return new int[]{left(arr,t),right(arr,t)};   
    }
    public static int left(int[] arr, int t) {
        if (arr == null || arr.length < 1) {
            return -1;
        }
        int ans = -1;
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int m = l + ((r - l) >> 1);
            if (arr[m] == t) {
               ans = m;
               r = m - 1;
            } else if (arr[m] < t) {
                l = m +1;
            } else {
                // arr[m] > t
                r = m - 1;
            }
        }
        return ans;
    }
    public static int right(int[] arr, int t) {
        if (arr == null || arr.length < 1) {
            return -1;
        }
        int ans = -1;
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int m = l + ((r - l) >> 1);
            if (arr[m] == t) {
               ans = m;
               l = m + 1;
            } else if (arr[m] < t) {
                l = m +1;
            } else {
                // arr[m] > t
                r = m - 1;
            }
        }
        return ans;
    }
}

时间复杂度 O(logN)。

局部最大值问题

思路

假设数组长度为N，首先判断0号位置的数和N-1位置的数是不是峰值位置。

0号位置只需要和1号位置比较，如果0号位置大，0号位置就是峰值位置，可以直接返回。

N-1号位置只需要和N-2号位置比较，如果N-1号位置大，N-1号位置就是峰值位置，可以直接返回。

如果0号位置和N-1在上轮比较中均是最小值，那么数组的样子必然是如下情况：

由上图可知，[0..1]区间内是增长趋势, [N-2...N-1]区间内是下降趋势。

那么峰值位置必在[1...N-2]之间出现。

此时可以通过二分来找峰值位置，先来到中点位置，假设为mid，如果中点位置的值比左右两边的值都大:

arr[mid] > arr[mid+1] && arr[mid] > arr[mid-1]

则mid位置即峰值位置，直接返回。

否则，有如下两种情况：

情况一：mid 位置的值比 mid - 1 位置的值小

趋势如下图：

则在[1...(mid-1)]

Dans un tableau ordonné, recherchez la position la plus à gauche qui est supérieure ou égale à un certain nombre

Exemple 1 :

Entrée : nums = [1,3,5,6], cible = 5

🎜Sortie : 2🎜🎜Explication : Si vous voulez pour utiliser numL'élément 5 inséré dans ce tableau doit être inséré à la position entre l'élément 3 et l'élément 5, c'est-à-dire la position 2. 🎜🎜Exemple 2 :🎜🎜Entrée : nums = [1,3,5,6], cible = 2🎜🎜Sortie : 1🎜🎜Explication : Si vous souhaitez insérer 2 dans le tableau num L'élément doit être inséré entre l'élément 1 et l'élément 3, c'est-à-dire la position 1. 🎜🎜Exemple 3 :🎜🎜Entrée : nums = [1,3,5,6], cible = 7🎜🎜Sortie : 4🎜🎜Explication : Si vous souhaitez insérer 7 dans le tableau num L'élément doit être inséré à la fin du tableau, c'est-à-dire à la position 4. 🎜🎜Vous pouvez savoir grâce à l'exemple ci-dessus que l'essence de cette question est de trouver la position la plus à gauche qui est supérieure ou égale à un certain nombre dans un tableau ordonné. Si elle n'existe pas, renvoyez la longueur du tableau (en indiquant. qu'il est inséré à la position finale)🎜🎜Nous n'avons qu'à effectuer des modifications simples basées sur l'exemple ci-dessus, lorsque nous trouvons la position qui remplit les conditions, nous retournons<.>🎜

public class LeetCode_0162_FindPeakElement {
    public static int findPeakElement(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }
        int l = 0;
        int r = nums.length - 1;
        if (nums[l] > nums[l + 1]) {
            return l;
        }
        if (nums[r] > nums[r - 1]) {
            return r;
        }
        l = l + 1;
        r = r - 1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]) {
                return mid;
            }
            if (nums[mid] < nums[mid + 1]) {
                l = mid + 1;
            } else if (nums[mid] < nums[mid - 1]) {
                r = mid - 1;
            }
        }
        return -1;
    }
}

🎜Dans cette question, parce que vous devez trouver la position la plus à gauche, donc lorsquevous rencontrez l'égalité, il vous suffit d'abord d'enregistrer la position, sans revenir directement, puis de continuer vers la gauche pour savoir s'il y a est une position vers la gauche qui remplit les conditions. 🎜🎜En même temps, lorsque vous rencontrez arr[m] > t, vous devez également enregistrer la position m à ce moment-là, car cela peut également être un endroit qui satisfait aux conditions. 🎜🎜Code : 🎜rrreee🎜La complexité temporelle de l'ensemble de l'algorithme est O(logN). 🎜🎜Trouver la première et la dernière position d'un élément dans un tableau trié🎜🎜🎜🎜Réflexion🎜🎜Cette question est également résolue par la dichotomie. Lorsqu'un élément est trouvé par dichotomie, ne vous précipitez pas en arrière, mais continuez à chercher vers la gauche (droite) pour voir si vous pouvez trouver plus La valeur à faire correspondre pour la position gauche (droite). 🎜🎜Le code est le suivant : 🎜rrreee🎜Complexité temporelle O(logN). 🎜🎜Problème de maximum local🎜🎜🎜🎜 Idée 🎜🎜 En supposant que la longueur du tableau est N, déterminez d'abord si le nombre à la position 0 et le nombre à la position N-1 Les positions sont des positions de pointe. 🎜🎜La position 0 doit uniquement être comparée à la position 1. Si la position 0 est plus grande, le 0code> position C'est la position maximale et peut être renvoyée directement. 🎜🎜La position N-1 doit uniquement être comparée à la position N-2 Si la position N-1 est plus grande, <. code>N Position -1 est la position maximale et peut être renvoyée directement. 🎜🎜Si la position 0 et N-1 sont toutes deux des valeurs minimales lors du dernier tour de comparaison, alors le tableau doit ressembler à ce qui suit : 🎜🎜🎜🎜Comme le montre l'image ci-dessus, [0..1 ]L'intervalle est une tendance croissante, et l'intervalle [N-2...N-1] est une tendance descendante. 🎜🎜Ensuite, la position du pic doit apparaître entre [1...N-2]. 🎜🎜À ce stade, vous pouvez trouver la position maximale par bissection. Allez d'abord à la position médiane, en supposant qu'elle est milieu si la valeur de la position médiane est supérieure. que les valeurs sur les côtés gauche et droit :🎜rrreee🎜La position milieu est la position maximale et est renvoyée directement. 🎜🎜Sinon, on a les deux situations suivantes : 🎜🎜Cas 1 : La valeur de la position médiane est inférieure à la valeur de la position médiane - 1 🎜🎜La tendance est la suivante : 🎜🎜🎜🎜 continuera dans le [1...(mi- 1)] intervalle Deux points. 🎜🎜Cas 2 : La valeur de la position médiane est inférieure à la valeur de la position médiane + 1🎜🎜La tendance est : 🎜🎜🎜🎜

则在[(mid+1)...(N-2)]区间内继续上述二分。

完整代码

public class LeetCode_0162_FindPeakElement {
    public static int findPeakElement(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }
        int l = 0;
        int r = nums.length - 1;
        if (nums[l] > nums[l + 1]) {
            return l;
        }
        if (nums[r] > nums[r - 1]) {
            return r;
        }
        l = l + 1;
        r = r - 1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]) {
                return mid;
            }
            if (nums[mid] < nums[mid + 1]) {
                l = mid + 1;
            } else if (nums[mid] < nums[mid - 1]) {
                r = mid - 1;
            }
        }
        return -1;
    }
}

时间复杂度O(logN)。

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!