【数据结构】【查找】二分查找

二分查找的核心思想就是根据有序数组的中间值判断目标所在的区间，每比较一次目标所在的范围都会缩小一半，当目标值和中间值相等的时候就找到了该目标值对应的数组下标，查找成功；当low>heigh的时候，就表明没有找到对应的元素，查找失败。

一、递归方式的二分查找

import java.util.Scanner;

public class BitSearch{
        public static void main(String args[]){
                Scanner scanner=new Scanner(System.in);
                int total=scanner.nextInt();
                int[] array=new int[1024];
                for(int i=0;i<total;i++){
                        array[i]=scanner.nextInt();
                }
                int aim=scanner.nextInt();
                int resultIndex=bitSearch(array,aim,0,total-1);
                if(resultIndex==-1){
                        System.out.println("没有找到目标！");
                }else{
                        System.out.println("查找到的索引值为："+resultIndex);
                        System.out.println(array[resultIndex]);
                }
        }
        public static void output(int[] array,int total){
                for(int i=0;i<total;i++){
                        System.out.print(array[i]+" ");
                }
                System.out.println();
        }
        public static int bitSearch(int[] array,int aim,int start,int end){
                if(start<=end){
                        int mid=(start+end)/2;
                        if(array[mid]==aim){
                                return mid;
                        }
                        else if(array[mid]>aim){
                                return bitSearch(array,aim,start,mid-1);
                        }else{
                                return bitSearch(array,aim,mid+1,end);
                        }
                }
                return -1;
        }
}

 二、非递归方式的二分查找

只需要替换掉上面的查找方法即可：

 public static int bitSearch(int[] array,int aim,int start,int end){
                while(start<=end){
                        int mid=(start+end)/2;
                        if(array[mid]==aim){
                                return mid;
                        }else if(array[mid]<aim){
                                start=mid+1;
                        }else{
                                end=mid-1;
                        }
                }
                return -1;
        }

 三、测试方法

使用之前的MyRandom类，但是需要修改一下：

import java.util.Random;

public class MyRandom {
        public static void main(String args[]){
                int[] array=new int[1024];
                for(int i=0;i<1024;i++){
                        array[i]=i;
                }
                System.out.println("1024");
                for(int i=0;i<1024;i++){
                        System.out.print(array[i]+" ");
                }
                System.out.println();
                Random random=new Random();
                System.out.println(random.nextInt(1024));
  //            System.out.println(1024);
        }
}

 其中

Random random=new Random();
System.out.println(random.nextInt(1024));

用于能够差找到的情况下的测试；

 System.out.println(1024);

用于查找不到的情况下的测试（1024不在0-1023之间）

四、测试命令

java MyRandom | java BitSearch

 

 

如果找不到：