Java实现二分查找

描述：
给定一个排好序的数组arr和一个数字x，让你在数组中找到x的下标，如果没有就返回-1；

思路：
将数组二分，用数组中位数和x对比，如果中位数大于x，则去数组的左半边找，反之去右半边；
比方说数组是{1, 2, 3, 4, 5, 9}，x为9
第一次：我们用数组中位数，即3（偶数的话选择中间两个中较小的）和9对比，9比3大，所以我们要去右半边找，此时数组为{4, 5, 9}，以此递归，直至找到9=9；

实现：

public class HalfFind {
    public static void main(String[] args) {
        System.out.println("下标为：" + half(new int[]{1, 2, 3, 4, 5, 9}, 9, 0, 5));
    }

    //需要指定查找数组的边界left和right，如果不这样的话，new个新数组也能实现，但是浪费内存
    public static int half(int[] ints, int x, int left, int right) {
        if (ints == null || left > right || x < ints[left] || x > ints[right]) return -1;
        int center = (right + left) / 2;
        System.out.println("此次折半中位数下标为：" + center);
        if (ints[center] == x) {
            //如果相等，直接返回下标
            return center;
        } else if (ints[center] < x) {
            //如果小于，则去右半边继续找
            return half(ints, x, center + 1, right);
        } else {
            //如果大于，则去左半边继续找
            return half(ints, x, left, center - 1);
        }
    }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
 

运行结果：

此次折半中位数下标为：2
此次折半中位数下标为：4
此次折半中位数下标为：5
下标为：5

文章来源: huangjie.blog.csdn.net，作者：负债程序猿，版权归原作者所有，如需转载，请联系作者。

原文链接：huangjie.blog.csdn.net/article/details/114576667