二分查找

分析

  • 首先必须是有序数组

  • 先定义一个中心指针

  • 循环看查找的数是否和中心点相等

  • 若比中心点小肯定在它左边就继续对比左边，反之对比右边

  • 如果左边界大于右边界了就退出循环

代码

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
package 算法;

import java.util.Arrays;

public class 二分查找 {
    public static void main(String[] args) {
        int[] arr = {3, 14, 53, 214, 542, 748};
        System.out.println(binaryFind(arr, 111));
    }

    public static int binaryFind(int[] arr, int num) {
        int l = 0, r = arr.length-1;
        int mid = (l + r) / 2;
        while (l <= r) {
            if (arr[mid] == num) {
                return mid;
            }
            if (arr[mid] > num) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
            mid = (l + r) / 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
    	// 区间[l,r]被划分为[l,mid]和[mid + 1,r]时使用:
    	int bsearch_1(int l,int r){
    	  	while(l < r){
    	     	int mid = l + r >> 1; //取中间值
    	      if(check(mid)) r = mid;//如果处于右半边满足条件则答案在mid的左边包括mid也有可能
    	      else l = mid + 1; //不满足条件答案在mid的右边不包括mid
    	    }
    	  	return l;
    	}
    	// 区间[l,r]被划分为[l,mid-1]和[mid,r]时使用:
    	int bsearch_2(int l,int r){
    	  	while(l < r){
    	     	int mid = l + r + 1 >> 1; //取中间值 但是由于取得l=mid防止下标越界需要+1处理
    	      if(check(mid)) l = mid;//左半边满足条件答案在mid的右边并且包括mid
    	      else r = mid - 1;//处于右半边不满足条件答案在mid的左边不包括mid
    	    }
    	  	return l;
    	}
    	//浮点数二分
    double bsearch_3(double l,double r){
    	  while(r - l > 1e-6){ //这里需比答案要求高出两位才能保证精度正确
    	  	double mid = (l + r)/2; //取中点
    	    if(check(mid)) r = mid; //左右两边都有可能是答案,因为浮点数只能确定范围不能精确到某个位置
    	    else l = mid; 
    	  }
    	  return l;
    	}