查找算法

HeChuangJun约 4402 字大约 15 分钟

顺序(线性)查找

public static int seqSearch(int[] arr, int value) {
	for (int i = 0; i < arr.length; i++) {
		if(arr[i] == value) {
			return i;
		}
	}
	return -1;
}

二分/折半查找算法(递归和非递归)

只适用于从有序不重复的数组中进行查找(比如数字和字母等)，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的
算法复杂度O(㏒₂n)

//二分查找的非递归实现
class Solution {
    public int search(int[] nums, int target) {
        // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        //定义target在左闭右闭的区间里，[left, right]
        // 当left==right，区间[left, right]依然有效，所以用 <=
        while (left <= right) {
            int mid = left + ((right - left) / 2);//防止溢出 等同于(left + right)/2
            if (nums[mid] == target) {
                return mid;
            }
            else if (nums[mid] < target) {
                left = mid + 1;
            }
            else { // nums[mid] > target
                //如果是left<=right,则right=mid-1,
                //如果是left<right,则right=mid
                right = mid - 1;
            }
        }
        // 未找到目标值
        return -1;
    }
}
/**
* @param arr数组
* @param left左边的索引
* @param right右边的索引
* @param findVal要查找的值
* @return 如果找到就返回下标，如果没有找到，就返回 -1
*/
public static int binarySearch(int[] arr, int left, int right, int findVal) {
	// 当 left > right 时，说明递归整个数组，但是没有找到
	if (left > right) return -1;
	int mid = (left + right) / 2;
	int midVal = arr[mid];

	if (findVal > midVal) { // 向右递归
		return binarySearch(arr, mid + 1, right, findVal);
	} else if (findVal < midVal) { // 向左递归
		return binarySearch(arr, left, mid - 1, findVal);
	} else {
		return mid;
	}
}

/*
* 课后思考题： {1,8, 10, 89, 1000, 1000，1234} 当一个有序数组中，
* 有多个相同的数值时，如何将所有的数值都查找到，比如这里的 1000
* 思路分析
* 1. 在找到mid 索引值，不要马上返回
* 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
* 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
* 4. 将Arraylist返回
*/
public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {
	// 当 left > right 时，说明递归整个数组，但是没有找到
	if (left > right) return new ArrayList<Integer>();
	int mid = (left + right) / 2;
	int midVal = arr[mid];

	if (findVal > midVal) { // 向 右递归
		return binarySearch2(arr, mid + 1, right, findVal);
	} else if (findVal < midVal) { // 向左递归
		return binarySearch2(arr, left, mid - 1, findVal);
	} else {			
		List<Integer> resIndexlist = new ArrayList<Integer>();
		//向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
		int temp = mid - 1;
		while(true) {
			if (temp < 0 || arr[temp] != findVal) {//退出
				break;
			}
			resIndexlist.add(temp);
			temp -= 1; //temp左移
		}
		resIndexlist.add(mid);  //
		//向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
		temp = mid + 1;
		while(true) {
			if (temp > arr.length - 1 || arr[temp] != findVal) {//退出
				break;
			}
			resIndexlist.add(temp);
			temp += 1; //temp右移
		}
		return resIndexlist;
	}
}

插入查找

与二分查找的区别仅是求中值不同

要求数组有序，插值查找每次从自适应mid处开始查找。
将折半查找中的求mid 索引的公式 , low 表示左边索引left, high表示右边索引right.key就是前面我们讲的findVal
原公式:int mid = (left + right) / 2 = low + 1/2 * (right - low)
新公式:

p o s = l o w + (\frac{(k e y - A [l o w]) \cdot (h i g h - l o w)}{A [h i g h] - A [l o w]})

对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找, 速度较快.关键字分布不均匀的情况下，该方法不一定比折半查找要好
平均情况：O(log(log(n)))，比二分查找更快，适用于均匀分布的数据。
最坏情况：O(n)，如果数据分布不均匀，可能退化为线性查找。

/**
* @param arr 数组
* @param left 左边索引
* @param right 右边索引
* @param findVal 查找值
* @return 如果找到，就返回对应的下标，如果没有找到，返回-1
*/
public static int insertValueSearch(int[] arr, int left, int right, int findVal) { 
	//findVal < arr[0]  和  findVal > arr[arr.length - 1] 防止 mid 可能越界
	if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
		return -1;
	}
	// 求出mid, 自适应
	int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
	int midVal = arr[mid];
	if (findVal > midVal) { // 说明应该向右边递归
		return insertValueSearch(arr, mid + 1, right, findVal);
	} else if (findVal < midVal) { // 说明向左递归查找
		return insertValueSearch(arr, left, mid - 1, findVal);
	} else {
		return mid;
	}

}

斐波那契(黄金分割法)查找算法(可选)

黄金分割点是指把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽，因此称为黄金分割，也称为中外比。
斐波那契数列 {1, 1, 2, 3, 5, 8, 13, 21, 34, 55 } 发现斐波那契数列的两个相邻数的比例，无限接近黄金分割值0.618
斐波那契查找原理与前两种相似，仅仅改变了中间结点（mid）的位置，mid不再是中间或插值得到，而是位于黄金分割点附近，即mid=low+F(k-1)-1（F代表斐波那契数列）

F(k-1)-1推导过程：
- 由斐波那契数列 F[k]=F[k-1]+F[k-2] 的性质，可以得到（F[k]-1）=（F[k-1]-1）+（F[k-2]-1）+1 。
- 只要顺序表的长度为F[k]-1，则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两段。从而中间位置为mid=low+F(k-1)-1
- 类似的，每一子段也可以用相同的方式分割
- 但顺序表长度n不一定刚好等于F[k]-1，所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可，由以下代码得到,顺序表长度增加后，新增的位置（从n+1到F[k]-1位置），都赋为n位置的值即可。

	public static int maxSize = 20;
	public static int[] fib() {
		int[] f = new int[maxSize];
		f[0] = 1;
		f[1] = 1;
		for (int i = 2; i < maxSize; i++) {
			f[i] = f[i - 1] + f[i - 2];
		}
		return f;
	}
	/**
	* @param a  数组
	* @param key 我们需要查找的关键码(值)
	* @return 返回对应的下标，如果没有-1
	*/
	public static int fibSearch(int[] a, int key) {
		int low = 0;
		int high = a.length - 1;
		int k = 0; //表示斐波那契分割数值的下标
		int mid = 0; //存放mid值
		int f[] = fib(); //获取到斐波那契数列
		//获取到斐波那契分割数值的下标
		while(high > f[k] - 1) {
			k++;
		}
		//因为 f[k] 值可能大于a的长度，因此需要使用Arrays类，构造一个新的数组，并指向temp[],不足的部分会使用0填充
		int[] temp = Arrays.copyOf(a, f[k]);
		//实际上要使用a数组最后的数填充 temp
		//举例:temp = {1,8, 10, 89, 1000, 1234, 0, 0}  => {1,8, 10, 89, 1000, 1234, 1234, 1234,}
		for(int i = high + 1; i < temp.length; i++) {
			temp[i] = a[high];
		}
		// 使用while来循环处理，找到我们的数 key
		while (low <= high) {
			mid = low + f[k - 1] - 1;
			if(key < temp[mid]) { //我们应该继续向数组的前面查找(左边)
				high = mid - 1;
				//全部元素 = 前面的元素 + 后边元素 f[k] = f[k-1] + f[k-2]
				//因为 前面有 f[k-1]个元素,所以可以继续拆分 f[k-1] = f[k-2] + f[k-3]
				//即 在 f[k-1] 的前面继续查找 k-- 即下次循环 mid = f[k-1-1]-1
				k--;
			} else if ( key > temp[mid]) { // 我们应该继续向数组的后面查找(右边)
				low = mid + 1;
				//全部元素 = 前面的元素 + 后边元素 f[k] = f[k-1] + f[k-2]
				//因为后面我们有f[k-2] 所以可以继续拆分 f[k-1] = f[k-3] + f[k-4]
				//即在f[k-2] 的前面进行查找 k -=2 即下次循环 mid = f[k - 1 - 2] - 1
				k -= 2;
			} else { //找到
				if(mid <= high) {
					return mid;
				} else {
					return high;
				}
			}
		}
		return -1;
}

35搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

时间复杂度：O(logn)，其中 n 为数组的长度。二分查找所需的时间复杂度为 O(logn)。
空间复杂度：O(1)。我们只需要常数空间存放若干变量。
class Solution {
    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1, ans = n;
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            if (target <= nums[mid]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

34在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]

由于数组已经排序，因此整个数组是单调递增的，我们可以利用二分法来加速查找的过程。
考虑 target 开始和结束位置，其实我们要找的就是数组中「第一个等于 target 的位置」（记为 leftIdx）和「第一个大于 target 的位置减一」（记为 rightIdx）。
二分查找中，寻找 leftIdx 即为在数组中寻找第一个大于等于 target 的下标，寻找 rightIdx 即为在数组中寻找第一个大于 target 的下标，然后将下标减一。两者的判断条件不同，为了代码的复用，我们定义 binarySearch(nums, target, lower) 表示在 nums 数组中二分查找 target 的位置，如果 lower 为 true，则查找第一个大于等于 target 的下标，否则查找第一个大于 target 的下标。
最后，因为 target 可能不存在数组中，因此我们需要重新校验我们得到的两个下标 leftIdx 和 rightIdx，看是否符合条件，如果符合条件就返回 [leftIdx,rightIdx]，不符合就返回 [−1,−1]。
时间复杂度： O(logn) ，其中 n 为数组的长度。二分查找的时间复杂度为 O(logn)，一共会执行两次，因此总时间复杂度为 O(logn)。
空间复杂度：O(1) 。只需要常数空间存放若干变量。
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        } 
        return new int[]{-1, -1};
    }

    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值互不相同的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

时间复杂度：时间复杂度为 O(logn)，其中 n 是数组 nums 的长度。在二分查找的过程中，每一步会忽略一半的区间，因此时间复杂度为 O(logn)。
空间复杂度：O(1)。
class Solution {
    public int findMin(int[] nums) {
        int min = 0, n = nums.length;
        //求出旋转后的最小值所在的索引
        for (int l = 1, r = n - 1; l <= r;) {
            int m = (l + r) / 2;
            if (nums[0] < nums[m]) {//中间元素 nums[m] 位于数组中较大的那部分（即未旋转部分）。
              l = m + 1;
            } else { //否则，更新 r = m - 1，并设置 min = m，表示 m 可能是旋转点。
              r = m - 1;
              min = m;
            }
        }
        return nums[min];
    }
}

33搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值互不相同。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标从 0 开始计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你旋转后的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

时间复杂度： O(logn)，其中 n 为 nums 数组的大小。整个算法时间复杂度即为二分查找的时间复杂度 O(logn)。
空间复杂度： O(1) 。我们只需要常数级别的空间存放变量。
class Solution {
    public int search(int[] nums, int target) {
        int min = 0, n = nums.length;
        //求出旋转后的最小值所在的索引
        for (int l = 1, r = n - 1; l <= r;) {
            int m = (l + r) / 2;
            if (nums[0] < nums[m]) {//中间元素 nums[m] 位于数组中较大的那部分（即未旋转部分）。
              l = m + 1;
            } else { //否则，更新 r = m - 1，并设置 min = m，表示 m 可能是旋转点。
              r = m - 1;
              min = m;
            }
        }
        //为了在一个逻辑上连续的区间内进行二分查找。这里的 min 是通过第一部分的二分查找得到的旋转点的索引。
        //原来是[0,n-1]=>[min,min+n-1]
        //i = m % n;为了索引正常
        for (int l = min, r = l + n - 1; l <= r;) {
            int m = (l + r) / 2, i = m % n;
            if (target < nums[i]) {
              r = m - 1;
            } else if (target > nums[i]) {
              l = m + 1;
            } else {
              return i;
            }
        }
        return -1;
    }
}

4寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

思路：把数组 A 和数组 B 分别在 i 和 j 进行切割。将 i 的左边和 j 的左边组合成「左半部分」，将 i 的右边和 j 的右边组合成「右半部分」。
当 A 数组和 B 数组的总长度是偶数时，
  1、左半部分的长度等于右半部分 i + j = m - i  + n - j  , 也就是 j = ( m + n ) / 2 - i
  2、左半部分最大的值小于等于右半部分最小的值 max ( A [ i - 1 ] , B [ j - 1 ]）） <= min ( A [ i ] , B [ j ]））
  中位数=（左半部分最大值 + 右半部分最小值 ）/ 2=（max ( A [ i - 1 ] , B [  j  - 1 ]）+ min ( A [ i ] , B [ j ]）） /  2
当 A 数组和 B 数组的总长度是奇数时，
  1、左半部分的长度比右半部分大1 ，i + j = m - i  + n - j  + 1也就是 j = ( m + n + 1) / 2 - i
  2、左半部分最大的值小于等于右半部分最小的值 max ( A [ i - 1 ] , B [ j - 1 ]）） <= min ( A [ i ] , B [ j ]））
  中位数就是=左半部分最大值，也就是左半部比右半部分多出的那一个数。max ( A [ i - 1 ] , B [  j - 1 ]）

class Solution {
    //nums1短数组，nums2长数组
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 确保 nums1 是较短的数组
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.length;
        int n = nums2.length;
        //imin 和 imax 用于定义在 nums1 上进行二分查找的范围。
        //halfLen 是总长度的一半，我们将通过它来决定分割点的位置。
        int imin = 0, imax = m, halfLen = (m + n + 1) / 2;
        //maxOfLeft 和 minOfRight 将用来存储左半部分的最大值和右半部分的最小值。
        double maxOfLeft = 0, minOfRight = 0;
        //总是在较短的数组上进行二分查找，以减少搜索范围并提高效率。
        while (imin <= imax) {
            //在 nums1 上进行二分查找。i 是当前的中间点，而 j 是在 nums2 上与 i 对应的点。
            int i = (imin + imax) / 2;
            int j = halfLen - i;
            //如果 i < m 并且 nums2[j-1] > nums1[i]，说明 i 太小了，我们需要增大 i，因此 imin = i + 1。
            if (i < m && nums2[j-1] > nums1[i]) {
                // i 太小，必须增加
                imin = i + 1;
            } else if (i > 0 && nums1[i-1] > nums2[j]) {
                // i 太大，必须减少
                imax = i - 1;
            } else {
                // i 是完美的
                //中位数（奇数情况）
                if (i == 0) { maxOfLeft = nums2[j-1]; }//nums1 的左半部分是空的，因此 maxOfLeft 只能从 nums2 中取得。
                else if (j == 0) { maxOfLeft = nums1[i-1]; }// nums2 的左半部分是空的，因此 maxOfLeft 只能从 nums1 中取得。
                else { maxOfLeft = Math.max(nums1[i-1], nums2[j-1]); }// nums1[i-1] 和 nums2[j-1] 中的最大值作为 maxOfLeft。
                if ((m + n) % 2 == 1) {
                    return maxOfLeft;
                }
                //中位数（偶数情况）
                if (i == m) { minOfRight = nums2[j]; }
                else if (j == n) { minOfRight = nums1[i]; }
                else { minOfRight = Math.min(nums1[i], nums2[j]); }

                return (maxOfLeft + minOfRight) / 2.0;
            }
        }

        return 0.0;
    }
}