Algorithm Binary Search

algorithm

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you’ve narrowed down the possible locations to just one.

前言

    二分搜索是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

二分法搜索

二分法查找基本思想:

在进行二分法搜索前需要先对数据进行排序，定义left（数据集的开头），right（数据集结尾）两个变量，然后在这组数据中找到mid=(left+right)/2，然后将待查找元素与mid所指元素进行比较，如果相等将索引返回，如果查找元素大于mid所指元素，则将left向右移动即left=mid+1;如果查找元素小于mid所指元素，则将left向左移动即right=mid-1。重复以上过程直到left>right(因为此时表明并不存在待查找元素)

二分法搜索解析：


二分法搜索代码：

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
 * @Auther: Arsenal
 * @Date: 2020-03-22 22:09
 * @Description: 二分法查找
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1234};
        //int resIndex = recusionBinarySearch(arr, 0, arr.length - 1, 189);
        int resIndex = binarySearch(arr, 0, arr.length - 1, 89);
        System.out.println("resIndex = " + resIndex);
    }

    /**
     * 二分法查找
     * @param arr   需查询的数组
     * @param left  左下标
     * @param right 右下标
     * @param value 需查找的值
     * @return 找到返回下标，否找返回-1
     */
    public static int binarySearch(int[] arr, int left, int right, int value) {

        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] > value) {
                right = mid - 1;
            } else if (arr[mid] < value) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 递归二分法查找
     * @param arr   需查询的数组
     * @param left  左下标
     * @param right 右下标
     * @param value 需查找的值
     * @return 找到返回下标，否找返回-1
     */
    public static int recusionBinarySearch(int[] arr, int left, int right, int value) {
        int mid = (left + right) / 2;

        if (left > right) {
            return -1;
        }

        if (arr[mid] > value) { //向左递归
            return recusionBinarySearch(arr, left, mid - 1, value);
        } else if (arr[mid] < value) { //向右递归
            return recusionBinarySearch(arr, mid + 1, right, value);
        } else {
            return mid;
        }
    }
}

延伸

    2种二分法查找
    二分查找-菜鸟教程
    二分法查找（折半查找）
    韩顺平数据结构和算法
    Data Structure and Algorithms Binary Search

Article Title:Algorithm Binary Search

Article Author:Funing Ma

Release Time:2020-03-22 18:28:38

Last Update:2020-03-30 10:13:28

Original Link:https://mafuning.github.io/2020/03/22/2020-03-22-Algorithm-Binary-Search/

License Agreement: "CC-BY-SA-4.0"

Content
  1. 1. 前言
  2. 2. 二分法搜索
  3. 3. 延伸