欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分法小结

程序员文章站 2022-06-03 13:57:28
...

一个基础模板:

二分法小结

注解:

    1、mid的表达式之所以不写成mid=(start+end)/2;是因为start+end值可能溢出,而mid=start+(end-start)/2绝对没有溢出的可能,这是一种严谨。

    2、while里面的条件是(start+1<end)是因为这样子结束的时候start和end大部分是一左一右情况,也可能是重合的情况。


二分法模板的四点要素

• start+1<end

• start + (end - start) / 2

• A[mid] ==, <, >

• A[start] A[end] ? target

第一题:

二分法小结

public class Solution {
    /**
     * @param A: an integer sorted array
     * @param target: an integer to be inserted
     * @return: An integer
     */
    public int searchInsert(int[] A, int target) {
        // write your code here
        if(A==null||A.length==0)
        return 0;
        int size = A.length;
        
        int left = 0;
        int right = A.length-1;
        //找比target小的第一个元素
        while(left+1<right){
            int mid = left + (right - left)/2;
            if(A[mid]==target){
                right = mid;
            }else if(A[mid]>target){
                right = mid;
            }else{
                left= mid;
            }
        }
        
        if(A[left]>=target)
            return left;
        if(A[right]<target)
            return right+1;
        if(A[left]<target&&A[right]>=target)
                return left+1;
        return -1;
    }
}

第二题:

https://www.lintcode.com/problem/find-peak-element/description

二分法小结

思路:

        找中间的数,与他相邻的两个数比较。如果mid<mid-1,则证明前半段一定有峰值;如果mid<mid+1,则后半段有。若mid>mid-1&&mid>mid+1,则直接返回.

    

public class Solution {
    /*
     * @param A: An integers array.
     * @return: return any of peek positions.
     */
    public int findPeak(int[] A) {
       if(A==null||A.length==0)
       return -1;
       int begin = 1;
       int end = A.length-2;
       int mid = 0;
       while(begin+1<end){
           
           mid = begin +(end-begin)/2;
           if(A[mid]<A[mid+1])
           begin = mid;
           else if(A[mid]<A[mid-1])
           end = mid;
            else 
            return mid;
           
       }
       if(A[begin]>A[end]){
           return begin;
       }else
        return end;
    }
}

第三题:复原翻转数组
二分法小结
思路:三部翻转法。


如 4 5 1 2 3

第一步 4 5   1 2 3

第二步 5 4  3 2 1

第三步 1 2 3 4 5

注意:如果数组里面有重复数的话,getFirstIndex就不能用二分.

https://www.lintcode.com/problem/recover-rotated-sorted-array/description

二分法小结