java算法——二分法及其拓展

题目描述： 在一个无序数组中，任何相邻的两个数一定不相等，求规定范围内它局部最小的那个数 要求：计算的过程时间复杂度小于O（N）

思路：由于所有相邻的两个数一定不相等，若一个数的左侧或右侧出现了比他小的数则说明，自己本身一定不是局部最小，并且局部最小一定出现在其左侧或者右侧

package class01;
//二分法的详解与拓展
//(1)在一个有序数组中，找某个数是否存在
//（2）在一个有序数组中，找>=某个数最左侧的位置
//（3）局部最小值问题(指的就是左一个和右一个数均大于他自身)
//二分法除了可以找到一个数所在的位置，还可以用来找大于等于某一个数在数组中最左侧位置的情况。（一定是二分到结束的）
//题目描述 在一个无序数组中，任何相邻的两个数一定不相等，求规定范围内它局部最小的那个数 要求：计算的过程时间复杂度小于O（N）
//二分不一定只有有序才可以使用  当数据的特点确定结果出现在一半，另一半位置可以被舍去的时候就可以采用。
//0-N-1上必存在局部最小 直接取中点位置，如果M小于M-1也小于M+1则直接返回M，否则
//优化一个流程（1）数据状况（2）问题标准
//自己的理解：由于所有相邻的两个数一定不相等，若一个数的左侧或右侧出现了比他小的数则说明，自己本身一定不是局部最小，并且局部最小一定出现在其左侧或者右侧
public class Code04_ErFen {
    public static  int searchleft(int [] arr ,int x){
        int left=0;
        int right=arr.length-1;

        while(left<=right){
            int mid =left+((right-left)>>1);
            if(arr[mid]>=x){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        return left;
    }
//   public static  int searchjubu(int []arr,int x){
//       int left=0;
//       int right=arr.length-1;
//       while (left<=right){
//           int mid =left+((right-left)>>1);
//           if(mid-1>=0&&mid+1<arr.length){
//               if(mid==0&&arr[mid]<arr[mid+1]){
//                   return mid;
//               }else if(mid==arr.length-1&&arr[mid]<arr[mid-1]){
//                   return mid;
//               }
//               else if(arr[mid-1]>arr[mid]&&arr[mid+1]>arr[mid]){
//                   return mid;
//               }
//           }
//       }
//       return mid;
//
//   }
    public static void main(String[] args) {
        int [] arr= {1,2,2,2,3,4,5,5,5,6,7,7,7,8,8};

        System.out.println(searchleft(arr,8));
    }

}