小蓝xlanll

这个屌丝很懒，什么也没留下！

热门标签

二分查找的各种形式总结_二分查找五种

作者：小蓝xlanll | 2024-04-17 02:26:07

踩

二分查找五种

文章目录

1. 查找某个元素

这是最常规的一种查找，给定一个元素key, 如果key存在于数组中，返回key对应的下标，不存在则返回-1

[0,1,2,3,4,5,6,] : 如果key=1,查找结果返回1；key=7,查找结果返回-1

1.1 左闭右闭区间

left=0,right=n-1 n表示数组的长度

public static int binary_search(int nums[], int target) {
        if (nums == null || nums.length == 0)
            return -1;
        int left = 0, right = nums.length-1;
        while (left <= right) {//注意点1
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid-1;//注意点2
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1.2 左闭右开区间

left=0,right=n n表示数组的长度

public static int binary_search(int nums[], int target) {
        if (nums == null || nums.length == 0)
            return -1;
        int left = 0, right = nums.length;
        while (left < right) {//注意点1
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid;//注意点2
        }
        return -1;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

两种情况对比：

左闭右闭：
注意点1：因为right的取值是nums.length-1，因此while循环处需要使用<=号，此时当left==right==nums.length-1时，循环体中下标并不会越界；
注意点2：因为时左闭右闭区间，因此当mid被访问之后，当访问mid左边的元素时应该是[left.mid-1], 由于是左闭右闭区间，所以直接right=mid-1

左闭右开：
注意点1：因为right的取值是nums.length，因此while循环处需要使用<号，而不是<=, 因为当left==right==nums.length;时，循环体中的下标就有可能越界；
注意点2：因为时左闭右开区间，因此当mid被访问之后，当访问mid左边的元素时应该是[left.mid-1], 由于是左闭右开区间，因此当right=mid时，即[left,mid), [left.mid-1]等价于[left,mid)

2. 查找某个元素的最左出现位置

[1,2,2,2,2,3,4,5] key=2 返回最左边的2，下标为1

形式1

//左闭右闭形式
public static int binary_search(int nums[], int target) {
        if (nums == null || nums.length == 0)
            return -1;
        int left = 0, right = nums.length-1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)//找到不立即返回 而是压缩右边界
                right=mid-1;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid-1;
        }
        // target比nums数组中的所有数字都大--->left>=nums.length
        //先进行left范围的判断，防止后面数组访问越界
        //target不存在于数组中---->nums[left]!=target
        if(left>=nums.length||nums[left]!=target)
           return -1;
        return left;
        
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

形式2

//左闭右开形式
public static int binary_search(int nums[], int target) {
        if (nums == null || nums.length == 0)
            return -1;
        int left = 0, right = nums.length;
        while (left < right) {//注意点1
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                right=mid;//注意点2
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid;//注意点3
        }
        // target比nums数组中的所有数字都大或都小（target不存在）
        //先进行left范围的判断，防止后面数组访问越界
        if(left>=nums.length||nums[left]!=target)//注意点4
           return -1;
        return left;
        
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

形式3

public int binary_search_left(int arr[],int target)
	{
		int left=0,right=arr.length-1;
		while(left<=right)
		{
			int mid=left+(right-left)/2;
			if(arr[mid]>target)
				right=mid-1;
			else if(arr[mid]<target)
				left=mid+1;
			else if(arr[mid]==target)
			{
				//当前如果arr[mid]==target再进行判断
				//mid==0: 已经是最左边了  返回结果
				//mid!=0 但是arr[mid-1]不等于key 说明arr[mid]是最左边的
				//arr[mid-1]<arr[mid]=key....
				if(mid==0||arr[mid-1]!=target)
					return mid;
				else
					right=mid-1;
			}
		}
		return -1;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3. 查找某个元素的最右出现位置

[1,2,2,2,2,3,4,5] key=2 返回最右边的2，下标为4

形式1

//左闭右闭
public static int binary_search(int nums[], int target) {
        if (nums == null || nums.length == 0)
            return -1;
        int left = 0, right = nums.length-1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)//找到不立即返回 压缩左边界
                left=mid+1;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid-1;
        }
        // target比nums数组中的所有数字都小/大（target不存在）
        //先进行right范围的判断，防止后面数组访问越界
        //因为right可以取到，因此right<0时，[left,right]即为空
        if(right<0||nums[right]!=target)
           return -1;
        return right;//right可以取到 返回right
        
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

形式2

//左闭右开
public static int binary_search(int nums[], int target) {
        if (nums == null || nums.length == 0)
            return -1;
        int left = 0, right = nums.length;
        while (left < right) {//注意点1
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                left=mid+1;//注意点2
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid;//注意点3
        }
        // target比nums数组中的所有数字都小/大（target不存在）
        //先进行right范围的判断，防止后面数组访问越界
        //因为right取不到，因此right<=0时，[left,right)即为空
        if(right<=0||nums[right-1]!=target)
           return -1;
        return right-1;//因为right取不到 所以返回right-1
        
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

形式3

//升序
public int binary_search_right(int arr[],int target)
	{
		int left=0,right=arr.length-1;
		while(left<=right)
		{
			int mid=left+(right-left)/2;
			if(arr[mid]<target)
				left=mid+1;
			else if(arr[mid]>target)
				right=mid-1;
			else if(arr[mid]==target)
			{
			//mid==arr.length-1： mid是最后一个位置了 直接返回
			//mid不是最后一个位置 但是处于这种情况： arr[mid]=key<arr[mid+1]  因此mid是最右位置
				if(mid==arr.length-1||arr[mid+1]!=target)
					return mid;
				else
					left=mid+1;
			}
		}
		return -1;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4. 查找某个元素的左边界

4.1 非严格左边界

从key开始往左寻找第一个a[i]<=key

[1,3,4,5,7,9] 4的非严格左边界是4； 6的非严格左边界是5

public static int binary_search(int nums[], int target) {
        if (nums == null || nums.length == 0)
            return -1;
        int left = 0, right = nums.length-1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                return mid;//如果key存在 非严格左边界就是自己
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid-1;
        }
        //left表示小于target的元素的数量 所以最后一个小于的元素的下标就是left-1
        //如果target小于数组中的所有元素 left=0  结果返回-1 表示target没有左边界
        return left-1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4.2 严格左边界

从key开始往左寻找第一个a[i]<key
[1,3,4,5,7,9] 4的严格左边界是3； 6的严格左边界是5

public static int binary_search(int nums[], int target) {
        if (nums == null || nums.length == 0)
            return -1;
        int left = 0, right = nums.length-1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)//相等时不直接返回 而是继续往左寻找
            	right=mid-1;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid-1;
        }
         //left表示小于target的元素的数量 所以最后一个小于的元素的下标就是left-1
        //如果target小于数组中的所有元素 left=0  结果返回-1 表示target没有左边界
        return left-1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

5. 查找某个元素的右边界

5.1 非严格右边界

从key开始往右寻找第一个a[i]>=key

[1,3,4,5,7,9] 4的非严格右边界是4； 6的非严格右边界是7

public static int binary_search(int nums[], int target) {
        if (nums == null || nums.length == 0)
            return -1;
        int left = 0, right = nums.length-1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)//相等时直接返回 key存在的话 右边界即自己
            	return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid-1;
        }
        //left表示小于target的元素的数量 所以最后一个小于的元素的下标就是left-1
        //这里直接返回left 小于target的元素是[0...left-1] 则nums[left]>=target
        //如果left==nums.lebgth 说明targt大于数组中的所有元素
        return left;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

5.2 严格右边界

从key开始往右寻找第一个a[i]>key
[1,3,4,5,7,9] 4的严格右边界是5； 6的严格左边界是7

public static int binary_search(int nums[], int target) {
        if (nums == null || nums.length == 0)
            return -1;
        int left = 0, right = nums.length-1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)//相等时不直接返回 而是继续往左寻找
            	left=mid+1;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid-1;
        }
         //left表示小于等于target的元素的数量 所以最后一个小于等于的元素的下标就是left-1
        //这里直接返回left 小于等于target的元素是[0...left-1] 则nums[left]>target
         //如果left==nums.lebgth 说明targt大于数组中的所有元素
        return left;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/437684

二分查找的各种形式总结_二分查找 五种