目录

一：二分查找的条件

二：二分查找思想​​​​​​​

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

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

一：二分查找的条件

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，找到目标

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

package look;

public class BinarySearch {
	public static void main(String[] args) {
		int[] arr = new int[]{1,2,6,7,9};
		int i = search(arr, 1, 0, arr.length - 1);//(0 , 4)
		System.out.print(i);
	}
	public static int search(int[] arr, int target, int min, int max) {
		if(min > max || max < min) {
			return -1;
		}
		while(min <= max) {
			int mid = (min + max) / 2;
			if(arr[mid] == target) {
				return mid;
			}
			if(arr[mid] < target) {
				min = mid + 1;
			}else if(arr[mid] > target) {
				max = mid - 1;
			}else {
				return -1;
			}
		}
		return -1;
	}
}

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

package sort;

import java.util.Arrays;

public class InsertSort {
	public static void main(String[] args) {
		int[] arr = new int[] {1, 2, 3, 4, 5, 6};
		int i = select(arr, 0, arr.length - 1, 4);
		System.out.println(i);
	}
	public static int select(int[] array, int left, int right, int searchVal) {
		if(left > right || array[0] > searchVal || array[right] < searchVal) {
			return -1;
		}
		//插值查找
//		int mid = left + (right - left)*(searchVal - array[left])/(array[right] - array[left]);
		//二分查找
		int mid = (left + right)/2;
		int midValue = array[mid];
		if(midValue < searchVal) {
			return select(array, mid + 1, right, searchVal);
		}else if(midValue > searchVal) {
			return select(array, left, mid - 1, searchVal);
		}else {
			return mid;
		}
	}
}