一、算法

概述

折半查找( 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 <a.length ; 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);}//折半查找法，找到返回其下标，找不到返回失败标志：-1private 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]<key){//继续在右半区间找left=mid+1;}else {//继续在左半区间找right=mid-1;}}//如果循环结束还未触发return语句说明查找失败return -1;}//使用选择排序法先将数组变成递增有序的序列private static void sort(int a[]){for(int i=0;i<a.length-1;i++){int min=i;for(int j=i+1;j<a.length;j++){if(a[j]<a[min]){min=j;}}if(min!=i){int temp=a[min];a[min]=a[i];a[i]=temp;}}}}