2020-11-06算法二分查找

1106算法二分查找

一、算法

1.二分查找

package com.xinzhi;

/**
 * @author 荆少奇
 * @date 2020/11/6
 */
class BinarySearchNonRecursive {
        public static void main(String[] args) {
            //定义边界
            int[] arr = {15,85,35,155,247,84,694};
            int index = binarySearch(arr, 15);
            if (index != -1) {
                System.out.println("找到了，下标为：" + index);
            }
        }
    //处理边界
        private static int binarySearch(int[] arr, int target) {
            int left = 0;
            int right = arr.length - 1;
            //查找中间值mid，还没找到
            while (left <= right) {
                int mid = (left + right) / 2;
                if (arr[mid] == target) {
                    return mid;
                } else if (arr[mid] > target) {
                    right = mid; // 向左找
                } else {
                    left = mid; // 向右找
                }
            }
            return -1;
        }
}

2.时间复杂（O(n)）

时间复杂度（Time complexity）是一个函数，它定性描述该算法的运行时间。

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。

随机数

Random random = new Random();

获取当前时间

long data = System.currentTimeMillis();

3.String

char charAt(值) 语法：字符串名.charAt(值);　　返回值为 char 类型。从字符串中取出指定位置的字符

sta.getBytes() 指定数值转成byte类型

public String concat(String str) 将参数中的字符串str连接到当前字符串的后面，效果等价于"+"。

String trim() 截去字符串两端的空格，但对于中间的空格不处理。

regionMatches(boolean b, int firstStart, String other, int otherStart, int length) 从当前字符串的firstStart位置开始比较，取长度为length的一个子字符串，other字符串从otherStart位置开始，指定另外一个长度为length的字符串，两字符串比较，当b为true时字符串不区分大小写。

4.可变参数

工具类

带有“s”的是工具类

工具类绝大多数为静态类

Arrays的折半查找法

 int[] num = {15,85,35,155,247,84,694};
 int i = Arrays.binarySearch(num,694);
 System.out.println(i);

可变参数

 int sum = sum(1,5,8,3,7,57);
 System.out.println(sum);
 
 public static int sum(int... sum){
      int snum = 0;
      for (int i = 0; i < sum.length; i++) {
          snum += sum[i];
      }
      return snum;

可变参数必须放在最后，一个方法只有一个可变参数

单核排序和多核排序

单核

int[] num = {15,85,35,155,247,84,694};
Arrays.Sort(num);
    for (int unm: num) {
        System.out.println(unm);
    }

多核

int[] num = {15,85,35,155,247,84,694};
//paraller是多核
Arrays.parallelSort(num);
    for (int unm: num) {
        System.out.println(unm);
    }

扩容数组

int[] aa = Arrays.copyOf(num,100);
for (int unm:aa) {
   System.out.println(unm);
}

Math数学类

向上取整

@Test
   public void testMath(){
       System.out.println(Math.ceil(2.5));
   }

向下取整

 @Test
    public void testMath(){
        System.out.println(Math.floor(2.5));
    }

Data

public Date（）：分配Data对象并初始化此对象。以表示分配它的时间。

public Data（Long data）：分配Data对象并初始化此对象，以表示自从基准时间，即1970年1月1日00:00:00 以来的指定毫秒数

 Date data = new Date();
 long time = data.getTime();
 System.out.println(time);
 SimpleDateFormat simpleTimeZone = new SimpleDateFormat("yyyy-MM-dd hh:mm:ss");
 String forame = simpleTimeZone.format(data);
 System.out.println(forame);