顺序查找

二分查找​

活动地址：CSDN21天学习挑战赛

目录

​1.顺序查找

1.1 定义

1.2 说明

1.3 代码示例

1.4 复杂度

1.5 优缺点

2.二分查找

2.1 定义

2.2 说明

2.3 代码示例

2.4 复杂度

2.5 优缺点

2.6 实战

---

 

​1.顺序查找

1.1 定义

顺序查找是按照序列原有顺序对数组进行遍历比较查询的基本查找算法。

对于任意一个序列以及一个给定的元素，将给定元素与序列中元素依次比较，直到找出与给定关键字相同的元素，或者将序列中的元素与其都比较完为止。

1.2 说明

通过一个任意排序的元素序列，存放在数组中，给出一个元素看数组中是否有该元素

有的话，就返回元素下标，没有的话就返回 -1。

数组下标是从 0 开始的

1.3 代码示例

public class OrderSearch {
	/**
	 * 顺序查找
	 * @param  array [数组]
	 * @param  tmp   [需要查的元素]
	 * @return       [返回下标值]
	 */
	public static int ordersearch(int[] array, int tmp) {
		for (int i = 0; i < array.length; i++) {
			if (tmp == array[i]) {
				return i;
			}
		}
		return -1;
	}
	public static void main(String[] args){
	 	int[] arr = {3,2,8,7,6,4,};
	 	int key = 8;
	 	int result =ordersearch(arr,key);
	 	System.out.println(result);
	}
}

1.4 复杂度

1）时间复杂度 ：

最好: O(1); 即查一次就找到

最坏：O（n）,遍历完数组

平均：O（n）

2) 空间复杂度

O（1）；

1.5 优缺点

1）优点：算法简单，使用范围广，适合新人入门

                对表中记录的存储没有任何要求，顺序存储和链接存储都可以。

                对表中记录的有序性也没有要求，一个一个查找就对了。

2）缺点：查找效率较低，一个一个查找

2.二分查找

 

2.1 定义

二分查找又叫“折半查找”，通过一个有序数组一分为二，不断的缩小搜索区域，进而找到目标元素。

当查找表中没有目标元素时，最终会出现 low>high 的情况，此时就表明查找表中没有目标元素，查找失败。

以升序数列为例，比较一个元素与数列中的中间位置的元素的大小，如果比中间位置的元素大，则继续在后半部分的数列中进行二分查找；如果比中间位置的元素小，则在数列的前半部分进行比较；如果相等，则找到了元素的位置。每次比较的数列长度都会是之前数列的一半，直到找到相等元素的位置或者最终没有找到要找的元素。

2.2 说明

必须是一个升序的有序数组。

查到返回元素下标值

没找到返回 -1

2.3 代码示例

public class WorkArray {
 
     public static int binarySearch(int[] array,int toFind) {
        //数组和要找的数
        int left = 0;
        int right = array.length-1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(toFind < array[mid]) {
                //在左侧区域找
                right = mid - 1;
            }else if(toFind >array[mid]) {
                //在右侧区域找
                left = mid + 1;
            }else {
                //相等，找到了
                return mid;
            }
        }
        //循环结束，没找到
        return -1;
    }
    public static void main(String[] args) {
        int[] array = {1,2,3,4,5,6,7,8,9};
        System.out.println(binarySearch(array, 3));
    }
   
 
}

2.4 复杂度

1）时间复杂度：O(log N）

2）空间复杂度：O（1）

2.5 优缺点

1）优点：

比较次数少，查找速度快，平均性能好。

2）缺点：

二分查找算法只适用于有序的静态查找表，且通常选择用顺序表表示查找表结构

2.6 实战

题目：第一个错误的版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的

题目来源：力扣（LeetCode）

解析：

根据题目描述 “错误的版本之后的所有版本都是错的” ，说明给定的版本正确性列表是「有序的」，即以某个版本为分界点，左边（右边）都是正确（错误）版本。因此，考虑使用「二分查找」来查找首个错误版本。

将左右边界分别初始化为 11 和 nn，其中 nn 是给定的版本数量。设定左右边界之后，每次我们都依据左右边界找到其中间的版本，检查其是否为正确版本。如果该版本为正确版本，那么第一个错误的版本必然位于该版本的右侧，我们缩紧左边界；否则第一个错误的版本必然位于该版本及该版本的左侧，我们缩紧右边界。

代码示例

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
 
        int left = 1;
        int right = n;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
        
    }
}

时间复杂度：O（log n）

空间复杂度：O（1）