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;
    }

}
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
26
27
28
29
30
31
32
33
34
35

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;
    }
}
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
26
27
28
29