每日算法 | 704.二分查找

例题：704.二分查找

题目描述：

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

代码：

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                return mid;
            }
        }
        return -1;
    }
}

思路：

二分查找，顾名思义就是分两头找，那么我们会想到什么？没错！双指针！但是二分查找难的地方其实在于细节处，什么时候该 <=或者>=，什么时候该 +1或者-1，难的地方主要在这里。

二分查找的思路其实主要就是两端向中心进行双指针查找，这样做能够比一般的顺序遍历要快很多。但是要注意，二分查找只能在有序数组中使用。所以如果想在无序数组使用，我们要做的第一件事就是先排序数组了。

另外：

其实二分搜索是一个很公式化的方法，基本套模版就能出答案的那种。

这里细节不细讲，直接看labuladong的算法笔记里面讲的或者别人讲的会更好，labuladong算法笔记里面讲的算是比较齐全，但不是很好串起来理解。

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...; //right根据题目赋值，不过大部分都是nums.length() - 1

    while(...) {    //一般都是 left <= right
        int mid = left + (right - left) / 2;    
        //这里这样计算是因为防止mid太大导致溢出，和(right + left) / 2 是一样的，为的就是预防这两个值过大导致计算溢出
        if (nums[mid] == target) {
            ...    //①return mid; ②right = mid;(二分搜索不放过左侧边界)
        } else if (nums[mid] < target) {
            left = ...    //一般是 mid + 1
        } else if (nums[mid] > target) {    
            right = ...    //一般是 mid - 1 
        }
    }
    return ...;    //普通就 return -1,寻找左边界就 return left
    /*
        如果害怕结果越界的话，可以把上面的return ...;加强
        if (left == nums.length()) return -1;    //target比所有大返回-1
        return nums[left] == target ? left : -1;    //判断nums[left]是不是target
    */
}
//来源于：labuladong的算法笔记
//我就是看着学的，纯用脑子理解细节的时候差点猪脑过载），本篇

二分查找本身并不难，只是它的细节比较多。但是各个细节之间有联系，如果搞懂了的话也可能在脑中形成一套模版，不管是普通的找目标，还是不放过左/右边界，都能很流畅的写出来。

后日谈：

这里还是直接给出不放过左侧边界的二分搜索代码吧：

class Solution {
public int search(int[] nums, int target) {
  int left = 0;
  int right = nums.length - 1;
  while (left < right) {
      int mid = left + (right - left) / 2;
      if (nums[mid] == target) {
          right = mid;
      }
      if (nums[mid] < target) {
          left = mid + 1;
      }
      if (nums[mid] > target) {
          right = mid -1;
      }
  }
  if (nums[left] != target) {
      return -1;
  }
  return nums[left] == target ? left : -1;
}
}