【21天学习挑战赛】顺序查找和二分查找的小总结

​
​

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

顺序查找

什么是顺序查找

我们生活中经常使用到顺序查找
比如我们要在一堆扑克牌中找到一张牌,
我们要怎么找
最简单的方式就是一张张的找
这就是顺序查找的原理
顺序查找就是把数组从头遍历到尾,找到想要的数字

代码

for(int i=0;i<arr.length;i++){
    
	if(arr[i]==target){
    
		return i;
	}
}

时间复杂度

因为最差情况要遍历这个数组,
因此时间复杂度为O(n)

*二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

什么是二分查找

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

nums[m]<target,因此要在右边找

nums[m]==target,ans=5

代码

class Solution {
    
    public int search(int[] nums, int target) {
    
        int n=nums.length;
        int l=0;
        int r=n-1;
        while(l<=r){
    
            int m=l+(r-l)/2;
            if(nums[m]<target){
    
                l=m+1;
            }else if(nums[m]>target){
    
                r=m-1;
            }else{
    
                return m;
            }
        }
        return -1;    
    }
}

进阶:在一个有序数组中，找>=某个数最左侧的位置

一直二分到死

代码

	public static int nearestIndex(int[] arr, int value) {
    
		int L = 0;
		int R = arr.length - 1;
		int index = -1; // 记录最左的对号
		while (L <= R) {
     // 至少一个数的时候
			int mid = L + ((R - L) >> 1);
			if (arr[mid] >= value) {
    
				index = mid;
				R = mid - 1;
			} else {
    
				L = mid + 1;
			}
		}
		return index;
	}

同理,在一个有序数组中，找<=某个数最右侧的位置,也是同样的解法

	public static int nearestIndex(int[] arr, int value) {
    
		int L = 0;
		int R = arr.length - 1;
		int index = -1; // 记录最右的对号
		while (L <= R) {
    
			int mid = L + ((R - L) >> 1);
			if (arr[mid] <= value) {
    
				index = mid;
				L = mid + 1;
			} else {
    
				R = mid - 1;
			}
		}
		return index;
	}

进阶2:局部最小值问题

在一个无序数组中, 值有可能正, 负, 或者零, 数组中任由两个相邻的数一定不相等.
定义局部最小:
1.长度为1，arr[0]就是局部最小；
2.数组的开头，如果arr[0] < arr[1] ，arr[0]被定义为局部最小。
3.数组的结尾，如果arr[N-1] < arr[N-2] ，arr[N-1]被定义为局部最小。
任何一个中间位置i, 即数组下标1~N-2之间, 必须满足arr[i-1] < arr[i] <arr[i+1] ,叫找到一个局部最小。
请找到任意一个局部最小并返回。

解题思路

先单独看0位置和n-1位置，如果两边都不是局部最小，那如果将数组每个数在坐标轴上连线，那一定存在局部最小位置，从中间分开，如果中间位置不是局部最小，那不管是那一半，也存在局部最小，像这种构建类似排他性的东西，就能二分，

代码

	public static int getLessIndex(int[] arr) {
    
		if (arr == null || arr.length == 0) {
    
			return -1;
		}
		if (arr.length == 1 || arr[0] < arr[1]) {
    
			return 0;
		}
		if (arr[arr.length - 1] < arr[arr.length - 2]) {
    
			return arr.length - 1;
		}
		int left = 1;
		int right = arr.length - 2;
		int mid = 0;
		while (left < right) {
    
			mid = (left + right) / 2;
			if (arr[mid] > arr[mid - 1]) {
    
				right = mid - 1;
			} else if (arr[mid] > arr[mid + 1]) {
    
				left = mid + 1;
			} else {
    
				return mid;
			}
		}
		return left;
	}

二分总结

1)数据状况特殊
2)问题本身特殊

二分不一定要求有序
要看你问题是什么，要看你的数据状况是什么
只要你能够构建一种排他性的东西， 左右两侧有一半肯定有,另一半可能没有
如果你只找一个，砍一半就行了, 只要你能构建出类似于排他性的东西, 你就能二分,不一定要求数组有序