二分查找法是数组问题里比较经典的

入参 数组，元素个数 ，目标数

  1. int bSearch(int[] arr, int n, int target) {
  2.     //在[left...right]范围里寻找target
  3.     int left = 0;
  4.     int right = n - 1;
  5.     //left==right时数组还是有一个元素的 所以要写成left<=right
  6.     while (left <= right) {
  7.         int mid = (left + right) / 2;
  8.         if (arr[mid] == target) {
  9.             return mid;
  10.         }
  11.         if (target > arr[mid]) {
  12.             //在[mid+1...right]中查找
  13.             left = mid + 1;
  14.         } else {
  15.             //在[left...mid-1]中查找
  16.             right = mid - 1;
  17.         }
  18.     }
  19.     return -1;
  20. }

注意点

right可以为n-1也可以为n，上面是为n-1
如果为n，满足条件就为 寻找target的范围为 [left...right) 左闭右开
需要改动的地方为
while循环 while (left < right)
right = mid;

bug

在这其中有一个不易察觉的Bug，那就是mid赋值那一行
由于left和right都是int类型，当值足够大时会存在整型溢出
要尽量用减法，避免用加法
将 int mid = (left + right) / 2; 换成 int mid = left + (right - left) / 2; 即可

正确的程序

  1.     private static int bSearch(int[] arr, int n, int target) {
  2.         //在[left...right]范围里寻找target
  3.         int left = 0;
  4.         int right = n - 1;
  5.         //left==right时数组还是有一个元素的 所以要写成left<=right
  6.         while (left <= right) {
  7.             int mid = left + (right - left) / 2;
  8.             if (arr[mid] == target) {
  9.                 return mid;
  10.             }
  11.             if (target > arr[mid]) {
  12.                 //在[mid+1...right]中查找
  13.                 left = mid + 1;
  14.             } else {
  15.                 //在[left...mid-1]中查找
  16.                 right = mid - 1;
  17.             }
  18.         }
  19.         return -1;
  20.     }