1 int binarySearch(int[] nums, int target){ 2 if(nums == null || nums.length == 0) 3 return -1; 4 5 int left = 0, right = nums.length - 1; 6 while(left <= right){ 7 // Prevent (left + right) overflow 8 int mid = left + (right - left) / 2; 9 if(nums[mid] == target){ return mid; } 10 else if(nums[mid] < target) { left = mid + 1; } 11 else { right = mid - 1; } 12 } 13 14 // End Condition: left > right 15 return -1; 16 }
模板一思考：对于二分查找，选择判断条件是一个难点。
1.while()里到底是<=还是<,当我们选择<=的时候，就要记住当left>right才会退出循环，所以说我们已经把数组里的元素全都扫过一遍了
如果只是单纯的用target去找一个相等的数的话，当循环结束了就等于未找到，我们将return -1；
对于某些会出现死循环的场景<=就不适用了，假设我们去找无序数组的峰值。在边界条件下，我们始终是让mid和后一个数比较，
如果找到的后一个数较小，我们就收缩右区间，让right指向它。这样就差不多可以知道，如果我们用<=的话，当我们找到那个最小值的
时候，该值肯定是比后一个数小的，所以我们就一直执行right=mid,然后就死循环。但如果我们用<的话，当left=right，我们就退出了循环，
其实我们就已经找到了那个值，直接返回就行了。
1 int binarySearch(int[] nums, int target){ 2 if(nums == null || nums.length == 0) 3 return -1; 4 5 int left = 0, right = nums.length; 6 while(left < right){ 7 // Prevent (left + right) overflow 8 int mid = left + (right - left) / 2; 9 if(nums[mid] == target){ return mid; } 10 else if(nums[mid] < target) { left = mid + 1; } 11 else { right = mid; } 12 } 13 14 // Post-processing: 15 // End Condition: left == right 16 if(left != nums.length && nums[left] == target) return left; 17 return -1; 18 }
原文：https://www.cnblogs.com/szzla/p/12733492.html
