活动地址：21天学习挑战赛

目录

一、 算法

概述

算法过程

二、代码实践

三、复杂度分析

时间复杂度

空间复杂度

四、优缺点分析

优点

缺点

---

一、 算法

概述

        折半查找( Binary Search )也称二分查找，它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

算法过程

• 从表的中间记录开始，如果给定值和中间记录的关键字相等，则查找成功
• 如果给定值大于中间记录的关键字，则继续在右半区间进行查找
• 如果给定值小于中间记录的关键字，则继续在左半区间进行查找
• 重复操作，直到查找成功，或者在某一步中查找区间为空，即左右区间交错，则查找失败

 

---

 
 

二、代码实践

package TwentyOne_Challenge;
 
public class DayFive {
    public static void main(String[] args) {
        int []a={3,38,5,44,15,36,26,27,2,47,46,4,19,50,48};
        sort(a);
        System.out.print("递增序列如下：");
        for (int i = 0; i 
            System.out.print(a[i]+" ");
        }
        System.out.println();
        int result1=Search(a,15);
        int result2=Search(a,666);
        System.out.println("查找15的结果为："+result1);
        System.out.println("查找666的结果为："+result2);
    }
    //折半查找法，找到返回其下标，找不到返回失败标志：-1
    private static int Search(int a[],int key){
        //left,right表示左右区间的下标
        int left=0,right=a.length-1;
        //循环终止条件为左右区间发生交错
        while(left<=right){
            //取出中间元素的下标，下面的下法是为了防止数据量较大时发生溢出
            int mid=(right-left)/2+left;
            if(a[mid]==key){
                return mid;
            }else if(a[mid]
                //继续在右半区间找
                left=mid+1;
            }else {
                //继续在左半区间找
                right=mid-1;
            }
        }
        //如果循环结束还未触发return语句说明查找失败
        return -1;
 
    }
   //使用选择排序法先将数组变成递增有序的序列
    private static void sort(int a[]){
        for(int i=0;i1;i++){
            int min=i;
            for(int j=i+1;j
                if(a[j]
                    min=j;
                }
            }
            if(min!=i){
                int temp=a[min];
                a[min]=a[i];
                a[i]=temp;
            }
        }
 
    }
 
}
 

 

---

 

 

三、复杂度分析

时间复杂度

• 最好的情况

最好的情况当然是一发入魂啦，第一次就找到了目标值，所以其时间复杂度为常数级别O(1)

• 最坏的情况

最坏的情况是最后一次折半才找到目标值或者说最后没有找到即查找失败，但是元素个数是固定死的就是n,就像一根长度为n的竹子，每天折一半，最多能折的次数其实就是以2为底n的对数

综合以上两种情况，折半查找法的时间复杂度为：

 

空间复杂度

由于算法不会改变原有的集合，只是需要三个额外的辅助变量，所以空间复杂度为常数级O(1)

 

---

 

四、优缺点分析

优点

• 比较次数少，查询效率较高

缺点

• 对表结构的要求较高，只能用于顺序存储的有序表
• 查找前需要先排序，这本身也是一种费时的运算