算法-二分查询、拆半查询

算法-二分查询、拆半查询

1.它的基本思想是：将n个有序的排列的元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较。

2.比较结果有三种情况：

2.1 如果x=a[n/2]则找到x，算法终止。

2.2 如 果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。

2.3 如果x>a[n/2]，则我们只要在数组a的右 半部继续搜索x。

3.二分查询步骤

目标=33

二分查询步骤：

第1步：22,27,33,37,43,47,53,57,63,67,

第2步：22,27,33,37,

第3步：33,37,

结果=33

实例代码：

@Test
  public void test(){  
          Integer[] arr={22,27,33,37,43,47,53,57,63,67};  
          
          Integer kw=33;  
          System.out.println("目标="+kw);  
          Integer result = binarySearch(arr,kw);  
          System.out.println("结果="+result);  
  }  
    
  public int binarySearch(Integer[] arr, int keyword) {  
      int min = 0;  
      int max = arr.length - 1;
      int i=0;
      System.out.println("二分查询步骤：");
      while (min <= max && min <=arr.length - 1 && max <= arr.length - 1) {
          i++;  
          printStep(arr,i,max,min);      
          int middle = (max + min) >> 1; //右移一位，相当于除以2，即：（max+min）/2  
          if (keyword == arr[middle]) {//中间值等于目标值，责返回
              return arr[middle]; //返回结果  
          } else if (keyword < arr[middle]) {//目标值小于中间值，截止索引=中间值-1  
              max = middle - 1;  
          } else { //目标大于中间值，开始索引=中间值+1；  
              min = middle + 1;  
          }
      }  
      return -1; //没有查到结果  
  }   
  public void printStep(Integer[] arr,int index,int max,int min){
    System.out.print("第"+index+"步：");
    for(int n=min;n<=max;n++){
      System.out.print(arr[n]+",");
    }
    System.out.println();
  }