要点

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

举例

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

  • 找出判断的条件：用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;
          }
      }

• 无重复数字的旋转数组中的最小值

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

• 有重复数字的旋转数组中的最小值
  • 找出判断的条件：
  • 何时退出循环：
  • 代码

参考：链接