二分算法

前言

一、什么是二分呢？

首先让我们一起来玩一个猜数小游戏：
我随便想一个1～100的数字，你的目标是以最少的次数猜到这个数字。你每次猜测后，我会说小了、大了或对了。
那么让我想想你首先会猜什么呢？因为要求是最少的次数查找，不冒险的情况的话你应该会先猜50，因为这样不管我心里的数是比50大还是比50小你都排除了一半数字，下一次依旧在剩有的数字范围内猜中间的数字，这就是所谓的二分算法

二、使用

1.python模板

代码如下（示例）：

def binary_search(list,item):
    # low high用来跟踪要在其中查找的列表部分
    low=0
    high=len(list)-1   
    # 循环折半查找
    while low<=high:
        # 检查中间元素
        mid=(low+high)/2
        # 向下取整
        guess=list[mid]
        # 相等直接返回
        if guess==item:
            return mid
        # 猜的数比心里的数大，将mid-1赋值给high
        if guess>item:
            high=mid-1
        #  猜的数比心里的数小，将mid+1赋值给low   
        else:
            low=mid+1
    return None

2.Java例题展示

牛客 NC32求平方根
题目描述如下：
实现函数 int sqrt(int x).
计算并返回 x 的平方根（向下取整）
数据范围： 0 <= x < 2^{31}-10<=x<2

要求：空间复杂度 O(1)O(1)，时间复杂度 O(logx)O(logx)
示例1

输入：
2
返回值：
1

示例2

输入：
2143195649

返回值：
46294

代码如下（示例）：

 public int sqrt (int x) {
        // write code here
           if (x<2){   //小于2时直接返回x
           return x;
       }
       int left=1;
       int right=x/2;   //开根号都小于等于这个数的一半
       while (left<right){
           int mid=left+(right-left+1)/2;//求中间值
           int temp=x/mid;
           if (mid>temp){
               right=mid-1;
           }
           else 
               left = mid;
       }
       return left;
    }

总结

以上就是二分的算法原理，模板以及例题，希望对热爱学习的你有所帮助

二分搜索（Binary Search）

• 如何确定一个元素在数组中的位置？（假设数组里面全都是整数）

• 如果是无序数组，从第0个位置开始遍历搜索，平均时间复杂度：O(n)
  

• 如果是有序数组，可以使用二分搜索，最坏时间复杂度为O(logn)
  

（一）、二分搜索 — 思路

• 假设在[begin，end）范围内搜索某个元素 v，mid == （begin + end）/ 2
  ①、如果v < m，去[begin ， mid）范围内二分搜索
  ②、如果v > m，去[mid + 1， end）范围内二分搜索
  ③、如果v == m ，直接返回 mid
• end指的是数组的长度。
  

（二）、二分搜索 — 实例

（三）、二分搜索 — 实现

import org.junit.Test;
import java.util.Arrays;

/**
* 查找v在有序数组array中的位置
*/
public class BinarySearch {
    public int indexOf(int[] array, int v){
        if (array == null || array.length == 0) return -1;
        int begin = 0;
        int end = array.length;
        while (begin < end){
            int mid = (begin + end) >> 1;
            if (v < array[mid]){
                end = mid;
            }else if (v > array[mid]){
                begin = mid+1;
            }else {
                return mid;
            }
        }
        return -1;
    }
    @Test
    public void test(){
        int[] array = {2,4,8,8,9,13,10};
        System.out.println(Arrays.toString(array));
        System.out.println(indexOf(array,8));
    }
}
运行结果：
[2, 4, 6, 8, 9, 13, 10]
3

• 思考？？？
  如果存在多个重复的值，返回的是哪一个？
• 例如：[2，4， 8， 8， 9， 13， 10]
  我们通过运行上述的代码，可以看到，它的返回值是3，而不是2，因此我们可以得出结论如果存在多个重复的值，返回的值不确定。

（四）、二分搜索优化

• 在元素 v 的插入过程中，可以先用二分搜索出合适的插入位置，然后再将元素v插入。
  
• 要求二分搜索返回的插入位置：第1个大于 v 的元素位置
  ①、如果 v 是 5，返回 2
  ②、如果 v 是 1，返回 0
  ③、如果 v 是 15，返回 7
  ④、如果 v 是 8，返回 5

（1）、二分搜索优化 — 思路

• 假设在[begin，end）范围内搜索某个元素 v，mid == （begin + end）/ 2
  ①、如果v < m，去[begin ， mid）范围内二分搜索
  ②、如果v >= m，去[mid + 1， end）范围内二分搜索
• end指的是数组的长度。
  

（2）、 二分搜索优化 — 实例

import org.junit.Test;
import java.util.Arrays;

public class BinarySearch {
    /**
     * 查找v在有序数组array中待插入位置
     */
    public static int search(int[] array, int v){
        if (array == null || array.length == 0) return -1;

        int begin = 0;
        int end = array.length;
        while (begin < end){
            int mid = (begin + end) >> 1;
            if (v < array[mid]){
                end = mid;
            }else{
                begin = mid+1;
            }
        }
        return begin;
    }

    @Test
    public void test2(){
        int[] array = {2,4,8,8,8,12,14};
        System.out.println(Arrays.toString(array));
        System.out.println(search(array,5) == 2);
        System.out.println(search(array,1) == 0);
        System.out.println(search(array,15) == 7);
        System.out.println(search(array,8) == 5);
    }
}
运行结果：
[2, 4, 8, 8, 8, 12, 14]
true
true
true
true

其实这里的底数对于研究程序运行效率不重要，写代码时要考虑的是数据规模n对程序运行效率的影响，常数部分则忽略，同样的，如果不同时间复杂度的倍数关系为常数，那也可以近似认为两者为同一量级的时间复杂度。

二分查找：

二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.

时间复杂度无非就是while循环的次数！

总共有n个元素，

渐渐跟下去就是n,n/2,n/4,....n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数

由于你n/2^k取整后>=1

即令n/2^k=1

可得k=log2n,（是以2为底，n的对数）

因此二分查找的时间复杂度就是log(n)!

冒泡排序：

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值：

所以，冒泡排序最好的时间复杂度为O(n)。

 

若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

冒泡排序的最坏时间复杂度为:

 

综上，因此冒泡排序总的平均时间复杂度为