二分查找

要点

找出判断的条件
何时退出循环

举例

无重复数字的普通二分查找

找出判断的条件：用arr[mid]和target去比较。如果arr[mid] == target时，返回mid；如果arr[mid] > target时，说明要找的值在左边，right = mid - 1；arr[mid] < target时，说明要找的值在右边，left = mid + 1；如果退出循环时还没有找到匹配到的项，则直接返回-1。
何时退出循环：left <= right时执行循环体。

代码

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

有重复数字的左边界查找

找出判断的条件：
何时退出循环：

代码

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

无重复数字的旋转数组查找

找出判断的条件：
何时退出循环：

代码

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

有重复数字的旋转数组查找

找出判断的条件：
何时退出循环：

代码

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