java二分查找含二分查找代码

目录

一：二分查找的条件

二：二分查找思想

三：二分查找代码（循环）

四：二分查找代码（递归）

一：二分查找的条件

1.1 必须是顺序存储结构

1.2 必须有序序列

二：二分查找思想

当min > max || max < min的时候没有找到

不断的更改mid , 当mid所指向的值等于查找的值的时候查找成功

首先看一个数组，需要对这个数组进行操作。需要对33进行查找的操作，那么target 的值就是33

首先，对 left 的值和 right 的值进行初始化，然后计算 middle 的值
left = 0, right = size - 1
middle = (left (right - left) / 2 )

比较 nums[middle] 的值和 target 的值大小关系

if (nums[middle] > target)，代表middle向右所有的数字大于target
if (nums[middle] < target)，代表middle向左所有的数字小于target
既不大于也不小于就是找到了相等的值
nums[middle] = 13 < target = 33，left = middle 1

见下图：

循环条件为 while (left <= right)

此时，left = 6 <= right = 11，则继续进行循环

当前，middle = left ((right - left) / 2)，计算出 middle 的值
计算出 middle 的值后，比较 nums[middle] 和 target 的值，发现：

nums[middle] = 33 == target = 33，找到目标

三：二分查找代码（循环）

1.  
   package look;
2.  
    
3.  
   public class BinarySearch {
4.  
   public static void main(String[] args) {
5.  
   int[] arr = new int[]{1,2,6,7,9};
6.  
   int i = search(arr, 1, 0, arr.length - 1);//(0 , 4)
7.  
   System.out.print(i);
8.  
   }
9.  
   public static int search(int[] arr, int target, int min, int max) {
10.  
    if(min > max || max < min) {
11.  
    return -1;
12.  
    }
13.  
    while(min <= max) {
14.  
    int mid = (min max) / 2;
15.  
    if(arr[mid] == target) {
16.  
    return mid;
17.  
    }
18.  
    if(arr[mid] < target) {
19.  
    min = mid 1;
20.  
    }else if(arr[mid] > target) {
21.  
    max = mid - 1;
22.  
    }else {
23.  
    return -1;
24.  
    }
25.  
    }
26.  
    return -1;
27.  
    }
28.  
    }

四：二分查找代码（递归）

1.  
   package sort;
2.  
    
3.  
   import java.util.Arrays;
4.  
    
5.  
   public class InsertSort {
6.  
   public static void main(String[] args) {
7.  
   int[] arr = new int[] {1, 2, 3, 4, 5, 6};
8.  
   int i = select(arr, 0, arr.length - 1, 4);
9.  
   System.out.println(i);
10.  
    }
11.  
    public static int select(int[] array, int left, int right, int searchVal) {
12.  
    if(left > right || array[0] > searchVal || array[right] < searchVal) {
13.  
    return -1;
14.  
    }
15.  
    //插值查找
16.  
    // int mid = left (right - left)*(searchVal - array[left])/(array[right] - array[left]);
17.  
    //二分查找
18.  
    int mid = (left right)/2;
19.  
    int midValue = array[mid];
20.  
    if(midValue < searchVal) {
21.  
    return select(array, mid 1, right, searchVal);
22.  
    }else if(midValue > searchVal) {
23.  
    return select(array, left, mid - 1, searchVal);
24.  
    }else {
25.  
    return mid;
26.  
    }
27.  
    }
28.  
    }

这篇好文章是转载于：学新通技术网