首页 > > 程序设计 > Java技术 >

二分查找-最基本的实现-小白初识

2019-02-17 01:51:30来源：博客园阅读 ()

二分查找特别好理解，就类似于快排和归并当中用到的分治的思想，每次取中间数与目标数相比较，然后确定是大了还是小了，区间折半。

就比如：

小红选中了1-100中的某个数字（这个数字是56），要小明来猜，产生如下对话：

小明第一次猜测：68

小红：大了

小明第二次猜测：35

小红：小了

小明第三次猜测：58

小红：大了

小明第四次猜测：49

小红：小了

小明第五次猜测：54

小红：小了

小明第六次猜测：56

小红：bingo！！！

我们可以看到在上面的对话中，小明每次猜测都可以缩小区间，直到回答正确。

二分查找就是这样的，比如我们现在有数组8，11，19，23，27，33，45，55，67，98，用二分查找如下图：

　　每次都可以缩小一半的区间，我们可以看到区间变化如下：

　　当区间大小无限接近1的时候k = log2n，所以时间复杂度为O(logn)。

　　是不是特别好理解，下面是我用Java实现的简单的二分查找（备注：是最简单的实现，二分查找的变体很复杂还没掌握）

 1 package com.structure.search;
 2 
 3 /**
 4  * 二分查找法
 5  *
 6  * @author zhangxingrui
 7  * @create 2019-02-15 21:29
 8  **/
 9 public class BinarySearch {
10 
11     public static void main(String[] args) {
12         int[] nums = new int[]{4, 6, 9, 19, 30, 40, 500, 3450, 50004, 4334343};
13         System.out.println(binarySearch(nums, 0, nums.length - 1, 30));
14         System.out.println(binarySearch(nums, 50004));
15     }
16 
17     /**
18      * @Author: xingrui
19      * @Description: 二分查找法（针对有序数组且不存在重复元素-递归方式实现）
20      * @Date: 21:37 2019/2/15
21      */
22     private static int binarySearch(int[] nums, int p, int r, int k){
23         if(p > r)
24             return -1;
25 
26         int mid = (p + r) / 2;
27         if(nums[mid] == k)
28             return mid;
29 
30         if(k > nums[mid])
31             return binarySearch(nums, mid + 1, r, k);
32         else
33             return binarySearch(nums, p,  mid - 1, k);
34     }
35 
36     /**
37      * @Author: xingrui
38      * @Description: 二分查找法（针对有序数组且不存在重复元素-循环实现）
39      * @Date: 21:37 2019/2/15
40      */
41     private static int binarySearch(int[] nums, int k){
42         int p = 0;
43         int r = nums.length - 1;
44         while (p <= r){
45             int mid = (p + r) / 2;
46 
47             if(nums[mid] == k)
48                 return mid;
49 
50             if(k > nums[p])
51                 p = mid + 1;
52             else
53                 r = mid - 1;
54         }
55         return -1;
56     }
57 
58 }