算法-顺序查找和二分查找

顺序查找

顺序查找即遍历查找，使用一个for循环即可实现顺序查找

/**
 * 顺序查找
 */
public static int linearSearch(int[] data, int target) {
    for (int i = 0; i < data.length; i++) {
        if (data[i] == target)
            return i;
    }
    return -1;
}

二分查找

首先一点，二叉查找是针对已经排好序的序列，二分查找即每次取数组的中间值进行比较，有三种情况

• 目标值大于当前值，那么目标值只能在当前值右侧
• 目标值等于当前值，那么查找成功
• 目标值小于当前值，那么目标值只能在当前值左侧

java实现如下

/**
 * 二分查找
 */
public static int binarySearch(int[] data, int target) {
    int mid;
    int left = 0;
    int right = data.length;
    // 当有边界小于左边界时结束循环
    while (right >= left) {
        mid = (left + right) / 2;
        // 比较成功返回下标
        if (data[mid] == target)
            return mid;
        // 目标数据小于当前数据
        else if (data[mid] > target)
            right = mid - 1;
        // 目标数据大于当前数据
        else
            left = mid + 1;
    }
    return -1;
}