算法合集（1）——二分查找

前言

二分查找再很多面试中都会涉及，作为一种最常见的查找方式，用它来作为算法学习的开篇再合适不过了。

一、原理

折半查找
即对于要查找的目标值假设找5，先取数组的一半查找，取中间值4

对比发现，数组中间值4小于5，不在左边这段，这时候再从右半段数组查找，取右半段数组中间值6，

6大于5，所以说就在左边这段（黑色这段），只有一个元素，也就是要查找的5

二、例子

讲完了原理，看一题，看看能不能做出来

三、代码实现

package SuanFa;

import scala.util.Right;

import java.lang.annotation.Target;
import java.util.ArrayList;

public class ErFenChaZhao {
    /**
     * 二分查找
     * {12,18,23,32,41,51,52,83,90,113,124}
     */
    public static void main(String[] args) {
        int[] list={12,18,23,32,41,51,52,83,90,113,124};
        int i = ErFen(list, 90);
        System.out.println(i);
    }
    public  static int ErFen(int[] list,int target){
        int left=0;
        int right=list.length-1;
        int mid = 0;
        while(left<=right){
            mid=(left+right)/2;
            if (target<list[mid]){
                right=mid-1;
                System.out.println("====a====");
            }else if (target>list[mid]){
                left=mid+1;
                System.out.println("====b====");
            }else {
                System.out.println("====c====");
                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
30
31
32
33
34
35
36
37
38

四、结果演示

如图所示，一共查找两次。