二分查找

发表于

二分查找

二分查找是一种比较基础的算法，思路类似于小游戏-猜出0-100的某个数字，适用于数组有序的情况。二分查找不一定会比暴力方法快，二者都是不稳定的，具体用时和数据有关系。

二分查找的思路很简单，但是在真正去写二分查找时，会发现他的边界条件很难把控。

例题：

704. 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

提示：

  1. 你可以假设 nums 中的所有元素是不重复的。
  2. n 将在 [1, 10000]之间。
  3. nums 的每个元素都将在 [-9999, 9999]之间。

示例 1:

1
2
3
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

1
2
3
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

分享一下个人的思路：

  1. 记录目前可能最大和最小可能值的位置min（初始 0）、max（初始 length-1）
  2. 取最中间的位置（max+min），与target进行比较
  3. 若小于target，则min = 现在的位置+1、若大于target，则max = 现在的位置-1
  4. 当前位置 =（max+min）/ 2，循环，直至找到target或者max<min
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int search(int[] nums, int target) {
        
        int length = nums.length;
        int max = length-1;
        int min = 0;
        int p = (max+min)/2;
        while(min<=max){
            if(nums[p] == target){
                return p;
            } 
            else if(nums[p]<target){
                min = p+1;
                p = (min+max)/2;
                
            }
            else if(nums[p]>target){
                max = p-1;
                p = (max+min)/2;
            }
        }
        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
class Solution {
    public int search(int[] nums, int target) {
        
        int length = nums.length;
        //创建一个等长的数组，比较过对应位置改位1，否则保持0
        int[] search = new int[length];
        int max = length;
        int min = 0;
        int p = length/2;
        while(true){
            if(nums[p] == target){
                return p;
            } 
            else if(nums[p]<target&&search[p]==0){
                search[p] = 1;
                min = p;
                p = (p+max)/2;
                
            }
            else if(nums[p]>target&&search[p]==0){
                search[p] = 1;
                max = p;
                p = (p+min)/2;
            }
            else {
                return -1;
            }
        }
    }
}