【数据结构与算法】—— 二分查找

1. 二分查找的概念 二分查找指的是在排好序的数组中，找到目标元素。如果元素存在则返回元素的下标，不存在则返回-1. 下面以升序为例进行简单描述
2. 查找过程： 取数组中间元素与查找元素target比较。如果target等于中间元素则直接返回中间元素的下标，如果target小于数组中间元素则在数组左边查找，如果target大于数组中间元素则在右边查找。重复以上步骤。
3. 二分查找的时间复杂度 O(logn)
4. Java实现 4.1 迭代版本

1public int searchByLoop(int[] arr, int target) {
2    return searchByLoop(arr, 0, arr.length - 1, target);
3}
4
5private int searchByLoop(int[] arr, int low, int high, int target) {
6    while (low <= high) {
7        int mid = (low + high) / 2;
8        if (target == arr[mid]) {
9            return mid;
10        } else if (target < arr[mid]) {
11            high = mid - 1;
12        } else {
13            low = mid + 1;
14        }
15    }
16    return -1;
17}

4.2 递归版本

1public int searchByRecursion(int[] arr, int target) {
2    return searchByRecursion(arr, 0, arr.length - 1, target);
3}
4
5private int searchByRecursion(int[] arr, int low, int high, int target) {
6    int mid = (low + high) / 2;
7    if (target == arr[mid]) {
8        return mid;
9    }
10    if (low > high) {
11        return -1;
12    }
13    if (target < arr[mid]) {
14        return searchByRecursion(arr, low, mid - 1, target);
15    }
16    return searchByRecursion(arr, mid + 1, high, target);
17}
18

5. 数据结构系列代码地址 Github：https://github.com/bennetty74...