二分查找边界值问题归类

目录

一、问题描述

二、思路分析

三、代码实现

3.1  情况1对应的代码

3.2  情况2对应的代码

3.3  情况3对应的代码

四、总结

---

一、问题描述

     A:假设一个含有n个元素的数组，采用二分查找的方法寻找某个元素；

二、思路分析

     A:通过简单的数组进行推导，可以分为3类，这3类也可以相互转化

 

三、代码实现

3.1  情况1对应的代码

package cn.itcast_01;

import java.util.Scanner;

/*
 * 需求:在数组中使用二分查找某个数据，存在则返回其下标，不存在返回-1;
 */
class TestDemo {
	public static void main(String[] args) {
		// 定义一个数组
		int[] nums = { 1, 2, 3, 4, 5, 6, 7, 8 };
		int left = 0;
		int right = nums.length - 1;
		int value = -1;
		// 键盘录入数据
		System.out.println("请输入你要查找的数据:");
		Scanner sc = new Scanner(System.in);
		value = sc.nextInt();
		// 开始循环
		while (left <= right) {
			int mid = (right + left) >>> 1;
			if (nums[mid] > value) {
				right = mid - 1;
			} else if (nums[mid] < value) {
				left = mid + 1;
			} else {
				System.out.println("value:" + value + "在数组中的下标为" + mid);
				break;
			}
		}
		if (left > right) {
			System.out.println("数组中不存在" + value);
		}
	}
}

3.2  情况2对应的代码

package cn.itcast_01;

import java.util.Scanner;

/*
 * 需求:在数组中使用二分查找某个数据，存在则返回其下标，不存在返回-1;
 */
class TestDemo {
	public static void main(String[] args) {
		// 定义一个数组
		int[] nums = { 1, 2, 3, 4, 5, 6, 7, 8 };
		int left = 0;
		int right = nums.length - 1;
		int value = -1;
		// 键盘录入数据
		System.out.println("请输入你要查找的数据:");
		Scanner sc = new Scanner(System.in);
		value = sc.nextInt();
		// 开始循环
		while (left < right) {
			int mid = (right + left) >>> 1;
			if (nums[mid] > value) {
				right = mid;
			} else if (nums[mid] < value) {
				left = mid + 1;
			} else {
				System.out.println("value:" + value + "在数组中的下标为" + mid);
				break;
			}
		}
		if (left == right) {
			System.out.println("数组中不存在" + value);
		}
	}
}

3.3  情况3对应的代码

      A:这个和上面的代码除了right=nums.length其余的都一样；

四、总结

      A:也就是两种情况，想使用left<=right的循环条件时，只适合于前闭后闭的情况，left=mid+1，right=mid-1；

      B:另外一种情况是想使用left<right作为循环条件时，既适合于前闭后开的情况，也适合于前闭后闭的情况，

         left=mid+1，right=mid；

      C:以上代码均测试通过；