折半查找算法
Author anteoy@gmail.com | Posted 2017-03-29 15:25:00

运行时间中的对数

    前一篇文章中分治递归的时间复杂度为O(nlogn);对数最常出现的规律可概括为如下一般规律:

如果一个算法用常数时间O(1)将问题的大小削减为其的一部分(通常是二分之一),那么该算法就是O(logn).另一方面,如果一个算法用常数时间O(1)将问题的大小消减一个常数数量(如将问题减少1等等),那么这种sauna就是O(n)的。

折半查找简单引论问题

    求x在数组T[]中的坐标,如果不存在x,则返回-1

方案一

  1. 思路:直接穷举,进行遍历,时间复杂度O(n),线性增长

  2. 代码:

    public static <T extends Comparable<? super T>> int binarySearch1(T[] a, T x){
    
    
        for(int i = 0;i < a.length;i++){
            if (a[i].compareTo(x) == 0){//如果相等则直接返回
                return  i;
            }
        }
        for (T ason:a) {
    
    
        }
        return -1;
    }
    

方案二

  1. 思路:折半查找

  2. 代码: “` /**

    • 求x在数组T[]中的坐标,如果不存在x,则返回-1

    • 此方法使用折半查找 时间复杂度为O(logn)

    • @param a

    • @param x

    • @param

    • @return */ public static >int binarySearch2(T[] a,T x){

      int low = 0, high = a.length -1; while (low <= high){

      //折半
      int mid = (low + high) / 2;
      //a[mid]更小 查右半部分
      if(a[mid].compareTo(x) < 0){
          low = mid +1;
      }else
      //a[mid]更大 查左边部分
      if(a[mid].compareTo(x) > 0){
          high = mid -1 ;
      }else{//a[mid] == x
          return mid;
      }
      

      } return -1; } “`

完整代码如下:

```
    package com.anteoy.coreJava.tmp;

    /**
     * Created by zhoudazhuang
     * Date: 17-3-29
     * Time: 下午2:43
     * Description : 折半查找算法
     */
    public class BinarySearchAlgorithm {

        /**
         * 求x在数组T[]中的坐标,如果不存在x,则返回-1
         * 此方法使用折半查找 时间复杂度为O(logn)
         * @param a
         * @param x
         * @param <T>
         * @return
         */
        public static <T extends Comparable<? super T>>int binarySearch2(T[] a,T x){

            int low = 0, high = a.length -1;
            while (low <= high){

                //折半
                int mid = (low + high) / 2;
                //a[mid]更小 查右半部分
                if(a[mid].compareTo(x) < 0){
                    low = mid +1;
                }else
                //a[mid]更大 查左边部分
                if(a[mid].compareTo(x) > 0){
                    high = mid -1 ;
                }else{//a[mid] == x
                    return mid;
                }
            }
            return -1;
        }

        public static <T extends Comparable<? super T>> int binarySearch1(T[] a, T x){

            for(int i = 0;i < a.length;i++){
                if (a[i].compareTo(x) == 0){//如果相等则直接返回
                    return  i;
                }
            }
            for (T ason:a) {

            }
            return -1;
        }

        public static void main(String[] args) {
            Integer[] array = {1,6,7,8,9,12};
            Integer x = 7;
            System.out.println(binarySearch1(array,x));
            System.out.println(binarySearch2(array,x));
        }
    }

```

输出:

2
2

参考文献

《数据结构和算法分析第二版》