二分查找及其变形整理

二分查找

基础的二分

原理就不多说了,一个有序数组里查找某个数是否存在/返回索引

public false binarySearch(int[] array , int target){
    if (array == null) return false;
    int left = 0;
    int right = array,length - 1;

    while(left < right){
        int mid = left + ((right - left) >> 1);
            if (nums[mid] == target)
                return true;
            else if (nums[mid] > target)
                right = mid;
            else
                left = mid;
    }
    return false;
}

二分变形

主要的变形有以下几个

1. 多个target,找出最左边的那个/第一次出现

public static int binarySearchLeftIndex(int[] array , int target){
        int left = 0;
        int right = array.length - 1;
        int index = 0; //记录最左索引

        while (left <= right){
            int mid = left + ((right - left) >> 1);
            if (array[mid] >= target){
                index = mid;
                right = mid - 1;
            }else
                left = mid + 1;
        }
        return index;
    }

2. 多个target,找最右边那个/最后一次出现

public static int nearestRightIndex(int[] array , int target){
        int left = 0;
        int right = array.length - 1;
        int index = 0;

        while (left <= right){
            int mid = left + ((right - left) >> 1);
            if (array[mid] <= target){
                index = mid;
                left = mid + 1;
            }
            else
                right = mid - 1;
        }
        return index;
    }

3. 查找局部最小

定义局部最小的概念:

  • arr长度为1时, arr[0]是局部最小
  • arr长度为N(N > 1)时, 如果arr[0] < arr[1], 那么arr[0]是局部最小
  • 如果arr[N-1] < arr[N-2]时, 那么arr[N-1]是局部最小
  • 如果0 < i< N-1, 既有 arr[i] < arr[i - 1], 又有arr[i] < arr[i + 1], 那么arr[i]是局部最小
    给定一个无序数组arr, 已知arr中任意两个相邻的数都不相等. 写一个函数, 只需返回arr中任意一个局部最小出现的位置即可.

二分思路

public static int binarySearchMin(int[] nums){
        if (nums == null || nums.length == 0) return -1;//不存在
        if (nums.length == 1 || nums[0] < nums[1]) return 0;
        if (nums[nums.length - 1] < nums[nums.length - 2]) return nums.length - 1;

        int left = 1;
        int right = nums.length - 2;
        int mid = 0;

        while (left < right){
            mid = (left + right) / 2;
            //从左到右是上升趋势,则局部最小肯定在mid的左边
            if (nums[mid] > nums[mid - 1])
                right  = mid - 1;
            //从左到右是下降趋势,则局部最小肯定在mid右边
            else if (nums[mid] > nums[mid + 1])
                left = mid + 1;
            //nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]最低点
            else
                return mid;
        }
        return -1;
    }
  • 微信
  • 快加我微信吧~
  • QQ
  • 快加我QQ吧~
  • weinxin
Betterts

发表评论 取消回复