Java~利用二分查找完成牛客经典算法题--查找旋转数组的最小数字

实现一个简单的二分查找

/**
 * Created with IntelliJ IDEA.
 * Description: If you don't work hard, you will a loser.
 * User: Listen-Y.
 * Date: 2020-07-29
 * Time: 9:54
 */
public class BinarySearch {

    public static boolean binarySearch(int[] arr, int val) {

        if (arr.length == 0) {
            return false;
        }
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] > val) {
                right = mid - 1;
            } else if (arr[mid] < val) {
                left = mid + 1;
            } else {
                return true;
            }
        }
        return false;

    }
}

• 这个算法很简单 因为前提条件就是传进去的是一个有序的数组
• 找到这个找到数组的中间下标mid 如果array[mid] > val 说明我们要找的数字就在left~mid之间 我们就使右边下标right指向mid的前一个 然后进行循环
• 如果array[mid] < val 说明我们要找的数字就在mid~right之间 我们就使右边下标left指向mid的后一个 然后进行循环
• 直到array[mid] == val 就说明找到了
• 否则就使没找到

查找旋转数组的最小数字

题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
牛客连接 旋转数组的最小数字
实现

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
       
        if (array == null || array.length == 0) {
            return 0;
        }
        int left = 0;
        int right = array.length - 1;
        int mid = 0;
        while (array[left] >= array[right]) {

            if (right - left == 1) {
                mid = right;
                break;
            }
            mid = (left + right) >> 1;
            if (array[left] == array[right] && array[mid] == array[left]) {
                int result = array[left];
                for (int i = left +1; i < right; i++) {
                    if (array[i] > result) {
                        result = array[i];
                    }
                }
                return result;
            }
            if (array[mid] >= array[left]) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return array[mid];
    }
}

讲解

• 定义首尾下标，因为是非递减数组旋转，所以旋转最后可以看做成两部分，前半部分整体非递减，后半部分 整体非递减，前半部分整体大于后半部分
• 因为是非递减排序的数组的一个旋转并且是把最开始的若干个元素搬到数组的末尾 所以white判定条件是array[left] >= array[right]
• 所以，我们假设如下定义，left指向最左侧，right指向最右侧，mid为二分之后的中间位置。
  则，a[mid] > a[left],说明mid位置在原数组前半部分，进一步说明，目标最小值，在mid的右侧，让 left=mid
• a[mid] < a[left], 说明mid位置在原数组后半部分，进一步说明，目标最小值，在mid的左侧，让 right=mid
• 这个过程，会让[left, right]区间缩小
• 这个过程中，left永远在原数组前半部分，right永远在原数组的后半部分，而范围会一直缩小
  当left和right相邻时，right指向的位置，就是最小元素的位置
• 但是，因为题目说的是非递减，也就意味着数据允许重复，因为有重复发，就可能会有a[left] == a[mid] == a[right]的情况，我们就无法判定数据在mid左侧还是右侧。（注意，只要有两者不相等，我 们就能判定应该如何缩小范围）

本文地址：https://blog.csdn.net/Shangxingya/article/details/107668123