常见的边界控制问题

二分查找

例 【二分查找】  在有序数组中查找元素 k ，返回 k 所在的下标

在数组 [1,2,10,15,100] 中去寻找 15 ，15 的下标是 3 ；

二分查找思路：

代码实现：BinarySearch.java

package interview.loop;public class BinarySearch {/*** Searches element k in a sorted array.* @param arr a sorted array* @param k the element to search* @return index in arr where k is. -1 if not found.*/public int binarySearch(int[] arr, int k) {	//传入参数数组int a = 0;			//定义数组下标 a、bint b = arr.length;		//数组下标包含整个数组//二分查找要保证的条件// Loop invariant: [a, b) is a valid range. (a <= b)// k may only be within range [a, b).while (a < b) {int m = a + (b - a) / 2; // m = (a + b) / 2 may overflow! 防止内存溢出if (k < arr[m]) {		//k 与中间节点 m 做比较，要查找的数据在 m 的左边b = m;} else if (k > arr[m]) {	//要查找的数据在 m 的右边a = m + 1;} else {return m;}}return -1;		//查找不到则返回 -1}public static void main(String[] args) {	//测试用例BinarySearch bs = new BinarySearch();System.out.println("Testing normal data");	System.out.println(bs.binarySearch(new int[]{1, 2, 10, 15, 100}, 15));System.out.println(bs.binarySearch(new int[]{1, 2, 10, 15, 100}, -2));System.out.println(bs.binarySearch(new int[]{1, 2, 10, 15, 100}, 101));System.out.println(bs.binarySearch(new int[]{1, 2, 10, 15, 100}, 13));System.out.println("======");System.out.println("Testing empty or singleton data.");System.out.println(bs.binarySearch(new int[]{}, 13));System.out.println(bs.binarySearch(new int[]{12}, 13));System.out.println(bs.binarySearch(new int[]{13}, 13));System.out.println("======");System.out.println("Testing data of size 2.");System.out.println(bs.binarySearch(new int[]{12, 13}, 13));System.out.println(bs.binarySearch(new int[]{12, 13}, 12));System.out.println(bs.binarySearch(new int[]{12, 13}, 11));}
}

输出：