16 | 二分查找（下）：如何快速定位 IP 对应的省份地址

package com.controller.bootweb.demo.dsa;
public class BinarySearchVariation {
    // 二分查找变种：查找第一个出现的元素的索引    public static int findFirstOccurrence(int[] nums, int target) {        int low = 0, high = nums.length - 1;        int result = -1;  // 初始化为-1，表示未找到
        while (low <= high) {            int mid = low + (high - low) / 2;            if (nums[mid] == target) {                result = mid;  // 更新结果，但不停止搜索，继续向左查找第一个出现的元素                high = mid - 1;            } else if (nums[mid] < target) {                low = mid + 1;            } else {                high = mid - 1;            }        }
        return result;    }
    public static void main(String[] args) {        int[] sortedArray = {1, 2, 2, 4, 4, 4, 5, 6, 7};        int target = 4;
        int result = findFirstOccurrence(sortedArray, target);
        if (result != -1) {            System.out.println("The first occurrence of " + target + " is at index " + result);        } else {            System.out.println(target + " is not found in the array.");        }    }}

package com.controller.bootweb.demo.dsa;
public class BinarySearchVariation {
    // 二分查找变种：查找最后一个出现的元素的索引    public static int findLastOccurrence(int[] nums, int target) {        int low = 0, high = nums.length - 1;        int result = -1;  // 初始化为-1，表示未找到
        while (low <= high) {            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {                result = mid;  // 更新结果，但不停止搜索，继续向右查找最后一个出现的元素                low = mid + 1;            } else if (nums[mid] < target) {                low = mid + 1;            } else {                high = mid - 1;            }        }
        return result;    }
    public static void main(String[] args) {        int[] sortedArray = {1, 2, 2, 4, 4, 4, 5, 6, 7};        int target = 4;
        int result = findLastOccurrence(sortedArray, target);
        if (result != -1) {            System.out.println("The last occurrence of " + target + " is at index " + result);        } else {            System.out.println(target + " is not found in the array.");        }    }}

public class BinarySearchVariation {
    // 二分查找变种：查找第一个大于等于目标值的元素的索引    public static int findFirstGreaterOrEqual(int[] nums, int target) {        int low = 0, high = nums.length - 1;        int result = -1;  // 初始化为-1，表示未找到
        while (low <= high) {            int mid = low + (high - low) / 2;
            if (nums[mid] >= target) {                result = mid;  // 更新结果，但不停止搜索，继续向左查找第一个大于等于目标值的元素                high = mid - 1;            } else {                low = mid + 1;            }        }
        return result;    }
    public static void main(String[] args) {        int[] sortedArray = {1, 2, 3, 4, 5, 6, 8, 8, 10};        int target = 7;
        int result = findFirstGreaterOrEqual(sortedArray, target);
        if (result != -1) {            System.out.println("The first element greater than or equal to " + target + " is at index " + result);        } else {            System.out.println("No element greater than or equal to " + target + " found in the array.");        }    }}

public class BinarySearchVariation4 {
    // 二分查找变种：查找最后一个小于等于目标值的元素的索引    public static int findLastLessOrEqual(int[] nums, int target) {        int low = 0, high = nums.length - 1;        int result = -1;  // 初始化为-1，表示未找到
        while (low <= high) {            int mid = low + (high - low) / 2;
            if (nums[mid] <= target) {                result = mid;  // 更新结果，但不停止搜索，继续向右查找最后一个小于等于目标值的元素                low = mid + 1;            } else {                high = mid - 1;            }        }
        return result;    }
    public static void main(String[] args) {        int[] sortedArray = {1, 2, 3, 4, 5, 6, 8, 8, 10};        int target = 7;
        int result = findLastLessOrEqual(sortedArray, target);
        if (result != -1) {            System.out.println("The last element less than or equal to " + target + " is at index " + result);        } else {            System.out.println("No element less than or equal to " + target + " found in the array.");        }    }}

public class BinarySearchVariation {
    // 二分查找变种：在旋转数组中查找目标元素的索引    public static int searchInRotatedArray(int[] nums, int target) {        int low = 0, high = nums.length - 1;
        while (low <= high) {            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {                return mid;            }
            // 判断哪一部分是有序的            if (nums[low] <= nums[mid]) {  // 左半部分有序                if (target >= nums[low] && target < nums[mid]) {                    high = mid - 1;                } else {                    low = mid + 1;                }            } else {  // 右半部分有序                if (target > nums[mid] && target <= nums[high]) {                    low = mid + 1;                } else {                    high = mid - 1;                }            }        }
        return -1;  // 未找到目标元素    }
    public static void main(String[] args) {        int[] rotatedArray = {4, 5, 6, 7, 0, 1, 2};        int target = 0;
        int result = searchInRotatedArray(rotatedArray, target);
        if (result != -1) {            System.out.println("The target " + target + " is at index " + result + " in the rotated array.");        } else {            System.out.println("The target " + target + " is not found in the rotated array.");        }    }}

public class BinarySearchVariation {
    // 二分查找变种：搜索插入位置    public static int searchInsertPosition(int[] nums, int target) {        int low = 0, high = nums.length - 1;
        while (low <= high) {            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {                return mid;  // 目标元素已存在，返回索引            } else if (nums[mid] < target) {                low = mid + 1;            } else {                high = mid - 1;            }        }
        return low;  // 目标元素不存在，返回插入位置    }
    public static void main(String[] args) {        int[] sortedArray = {1, 3, 5, 6};        int target = 5;
        int result = searchInsertPosition(sortedArray, target);
        System.out.println("The target " + target + " should be inserted at index " + result);    }}

public class BinarySearchVariation7 {
    // 二分查找变种：寻找峰值    public static int findPeakElement(int[] nums) {        int low = 0, high = nums.length - 1;
        while (low < high) {            int mid = low + (high - low) / 2;
            if (nums[mid] > nums[mid + 1]) {                // 峰值可能在左侧                high = mid;            } else {                // 峰值可能在右侧（包括 mid 本身）                low = mid + 1;            }        }
        return low;    }
    public static void main(String[] args) {        int[] array = {1, 2, 3, 1};
        int peakIndex = findPeakElement(array);
        System.out.println("The peak element is at index " + peakIndex);    }}

package com.controller.bootweb.demo.dsa;
public class MatrixSearch {
    // 在二维矩阵中查找目标值    public static boolean searchMatrix(int[][] matrix, int target) {        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {            return false;        }
        int rows = matrix.length;        int cols = matrix[0].length;
        int row = 0, col = cols - 1;  // 从矩阵的右上角开始搜索
        while (row < rows && col >= 0) {            if (matrix[row][col] == target) {                return true;  // 找到目标值            } else if (matrix[row][col] < target) {                row++;  // 当前值小于目标值，向下移动            } else {                col--;  // 当前值大于目标值，向左移动            }        }
        return false;  // 未找到目标值    }
    public static void main(String[] args) {        int[][] matrix = {                {1, 4, 7, 11},                {2, 5, 8, 12},                {3, 6, 9, 16},                {10, 13, 14, 17}        };
        int target = 5;
        boolean found = searchMatrix(matrix, target);
        if (found) {            System.out.println("The target " + target + " is found in the matrix.");        } else {            System.out.println("The target " + target + " is not found in the matrix.");        }    }}

package com.controller.bootweb.demo.dsa;
public class FindMinInRotatedArray {
    // 在循环排序数组中查找最小值    public static int findMin(int[] nums) {        int left = 0, right = nums.length - 1;
        while (left < right) {            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {                // 最小值可能在右侧                left = mid + 1;            } else if (nums[mid] < nums[right]) {                // 最小值可能在左侧（包括 mid 本身）                right = mid;            } else {                // 无法确定在左侧还是右侧，缩小搜索范围                right--;            }        }
        return nums[left];    }
    public static void main(String[] args) {        int[] rotatedArray = {4, 5, 6, 7, 0, 1, 2};
        int minValue = findMin(rotatedArray);
        System.out.println("The minimum value in the rotated array is: " + minValue);    }}

package com.controller.bootweb.demo.dsa;
public class FirstMissingPositive {
    // 寻找缺失的第一个正数    public static int firstMissingPositive(int[] nums) {        int n = nums.length;
        // 将每个数字放到正确的位置，使得 nums[i] == i + 1        for (int i = 0; i < n; i++) {            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {                swap(nums, i, nums[i] - 1);            }        }
        // 查找第一个位置不满足 nums[i] == i + 1 的数字        for (int i = 0; i < n; i++) {            if (nums[i] != i + 1) {                return i + 1;            }        }
        // 如果数组中的所有数字都满足条件，则返回 n + 1        return n + 1;    }
    // 交换数组中两个元素的位置    private static void swap(int[] nums, int i, int j) {        int temp = nums[i];        nums[i] = nums[j];        nums[j] = temp;    }
    public static void main(String[] args) {        int[] nums = {3, 4, -1, 1};
        int missingPositive = firstMissingPositive(nums);
        System.out.println("The first missing positive is: " + missingPositive);    }}