1.1二分查找

二分查找，主要是针对基本有序的数据来进行查找target。

二分法的思想很简单，因为整个数组是有序的，数组默认是递增的。

1.1 使用条件

• 用于查找的内容逻辑上来说是需要有序的
• 查找的数量只能是一个，而不是多个

1.2 简介

• 首先选择数组中间的数字和需要查找的目标值比较 如果相等最好，就可以直接返回答案了
• 如果不相等
  • 如果中间的数字大于目标值，则中间数字向右的所有数字都大于目标值，全部排除
  • 如果中间的数字小于目标值，则中间数字向左的所有数字都小于目标值，全部排除

2 代码

• 循环条件要使用while(left<= right)，因为当(left== right)这种情况发生的时候，得到的结果是有意义的
• if(nums[mid] > target) ， right要赋值为 mid- 1， 因为当前的 nums[mid]
  一定不是 target ，需要把这个 mid位置上面的数字丢弃，那么接下来需要查找范围就是[left, mid- 1]

2.1 非递归方法：

public class BinarySearch {public static void main(String[] args) {int [] nums = {1,2,3,4,5,9,10,11,19,25};int target = 19;/** 第一种方法：实例化对象，BinarySearch test = new BinarySearch();System.out.println("实例化对象调用："+search(nums,target));*///第二种方法：直接通过类名.方法名调用，方法为static的时候使用System.out.println("下标为："+ BinarySearch.search(nums,target));}//非递归查找public static int search(int[] nums, int target){int len = nums.length;int left=0;int right=len-1;//目标存在的区间可能在两者之间 注意"="号while(left<=right){int mid = (left+(right-left)/2);if(nums[mid]==target){return mid;}else{if(nums[mid]>target){right = mid - 1 ;}else{left = mid +1 ;}}}return -1;}}

2.2 递归查找

public class BinarySearch02 {public static void main(String[] args) {int [] nums = {1,2,3,4,5,9,10,11,19,25};int target = 19;//递归需要传参数int left = 0;int len = nums.length;int right = len-1;//直接通过类名.方法名调用，方法为static的时候使用System.out.println("下标为："+ BinarySearch02.Digui(nums,left,right,target));}//递归查找public static int Digui(int[] nums, int left, int right, int target) {while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] > target) {return Digui(nums, left, mid - 1, target);} else if (nums[mid] < target) {return Digui(nums, mid + 1, right, target);} else {return mid;}}return -1;}
}