算法：二分查找（Java）

题目

给定一个按照升序排列的整数数组array，和一个目标值target。找出给定目标值在数组中的索引

实列1：array：1, 5, 8, 11, 19, 22, 31, 35, 40, 45, 48, 49, 50 target：48

输出结果：10

实现过程

1. 定义左边界L，右边界R，确定搜索范围，循环执行二分查找（2、3步）
2. 获取中间索引M=Floor((L+R)/2)
3. 索引M所对应的值array[M]与目标值target进行比较
   • array[M] == target，表示找到，返回中间索引
   • array[M] > target，中间值右侧的其他元素都大于target，无需比较，中间索引M左边去找，M-1设置为右边界，重新查找
   • array[M] < target，中间值左侧的其他元素都小于target，无需比较，中间索引M右边去找，M+1设置为左边界，重新查找
4. 当L>R时，表示没有找到，应该结束循环。

动图演示

二分查找与顺序查找的对比：

代码实现

/**
 * @Author zzw2000
 * @Date 2022年08月15日 19:14
 * @Description 二分查找
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] array = {1, 5, 8, 11, 19, 22, 31, 35, 40, 45, 48, 49, 50};
        int target = 47;
        int index = binarySearch(array, target);
        System.out.println(index);
    }

    /**
     * 二分查找，找到返回元素索引，否则返回-1
     *
     * @param array  有序数组
     * @param target 目标元素
     * @return 找到返回元素索引，否则返回-1
     */
    private static int binarySearch(int[] array, int target) {
        int l = 0, r = array.length - 1, m; //左边界l，右边界r，中间元素m
        while (l <= r) {
            m = (l + r) >>> 1; //计算中间索引
            if (array[m] == target) {
                return m;
            } else if (array[m] > target) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return -1;
    }
}

#include <stdio.h>

/**
 * 二分查找
 * @param array  有序数组
 * @param target 目标元素
 * @param length 数组长度
 * @return
 */
int binarySearch(const int *array, int target, int length);

int main() {
    int array[13] = {1, 5, 8, 11, 19, 22, 31,
                     35, 40, 45, 48, 49, 50};
    int target = 48;
    int length = sizeof(array) / sizeof(array[0]);
    int index = binarySearch(array, target, length);
    printf("%d在数组array中的位置是%d\n", target, index);
    return 0;
}

int binarySearch(const int *array, int target, int length) {
    int low = 0, high = length - 1, middle;
    while (low <= high) {
        middle = (low + high) >> 1;
        if (array[middle] == target) {
            return middle;
        } else if (array[middle] > target) {
            high = middle - 1;
        } else {
            low = middle + 1;
        }
    }
    return 0;
}