二分查找算法

发表于 | 分类于 | | 阅读次数

二分查找算法(Java)

logo

1.二分查找又称折半查找，它是一种效率较高的查找方法。

2.二分查找要求：（1）必须采用顺序存储结构 （2）.必须按关键字大小有序排列

3.原理：将数组分为三部分，依次是中值（所谓的中值就是数组中间位置的那个值）前，中值，中值后；将要查找的值和数组的中值进行比较，若小于中值则在中值前 面找，若大于中值则在中值后面找，等于中值时直接返回。然后依次是一个递归过程，将前半部分或者后半部分继续分解为三部分。

4.实现：二分查找的实现用递归和循环两种方式

代码如下:

1.非递归 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 *@description 二分查找非递归
 *@return 所查询的数字索引 查询不到返回-1
 /
public static int binarySearch(int[] arr, int target){
   int left = 0;
   int right = arr.length - 1;
   while(left <= right){
     int middle = (left + right) / 2;
     if(target = arr[middle]){
       return middle;
     }
     if(target > array[middle]){
       left = middle + 1;
     }else{
       right = middle - 1;
     }
   }
   return -1;
}
//程序入口
public static void main(String[] args){
  int[] arr = {1,5,5,7,9,10,34};  //必须为已排好序的数组
  System.out.println(binarySearch(arr, 9));
}

结果: 4

2.递归实现二分查找

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int binarySearchByRecursive(int[] arr, int left, int right, int target){
  int middleIndex = (right + left) / 2;
  if(left > right || target < arr[left] || target > arr[right]){
    return -1;
  }
  if(target > arr[middleIndex]){
    return binarySearchByRecursive(arr, middleIndex+1, right, target)
  }else if(target < arr[middleIndex]){
    return binarySearchByRecursive(arr, left, middleIndex - 1);
  }else{
    return middleIndex;
  }
}
//程序入口
public static void main(String[] args){
  int[] arr = {1,5,5,7,9,10,34};  //必须为已排好序的数组
  System.out.println(binarySearch(arr, 9));
}

结果如非递归二分查找。