public static int binarySearch(int[] a, int key) { return binarySearch0(a, 0, a.length, key); } public static int binarySearch(int[] a, int fromIndex, int toIndex, int key) { rangeCheck(a.length, fromIndex, toIndex); return binarySearch0(a, fromIndex, toIndex, key); } // Like public version, but without range checks. private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) { int low = fromIndex; int high = toIndex - 1; while (low <= high) { int mid = (low + high) >>> 1; int midVal = a[mid]; if (midVal < key) low = mid + 1; else if (midVal > key) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found. }
为啥是mid + 1 ,mid - 1就一个下标感觉没差啊。
回答:调试之后再回想,发现没有什么差别,最终收拢到 low == high 的时候都能算出来,不会错过。
public class Source1_BinarySearch { public static int binarySearch(int[] a, int fromIndex, int toIndex, int key) { int low = fromIndex; int high = toIndex - 1; while (low <= high) { int mid = (low + high) >> 1; int midValue = a[mid]; // 小于 lo 指向中间,大于hi指向中间,等于直接返回 if (midValue < key) low = mid + 1; else if (midValue > key) high = mid - 1; else return mid; } return -1; } public static int binarySearch_Recursive(int[] a, int fromIndex, int toIndex, int key) { int low = fromIndex; int high = toIndex - 1; int result = -1; if (low <= high) { int mid = (low + high) >>> 1; int midValue = a[mid]; if(midValue < key) result = binarySearch_Recursive(a,mid +1,high + 1,key); else if (midValue > key) result = binarySearch_Recursive(a,low,mid + 1 -1,key); else return mid; } return result; } public static void main(String[] args) { int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int index = binarySearch_Recursive(a, 0, a.length, 11); System.out.println(index); } }
如对本文有疑问, 点击进行留言回复!!
Flink程序JDK8 运行一段时间后NullException解决
解决: java.lang.NoClassDefFoundError: org/apache/http/client/HttpClient
SpringBoot中定制异常页面(404页面配置提高用户体验)
DataGrip和IDEA无法连接上Mysql问题解决方法详解
Java基础语法(多态、类、接口、Date类、基本类型、系统类)
网友评论