稀疏数组搜索

有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。
示例1:
输入: words = [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”,”dad”, “”, “”], s = “ta”
输出：-1
说明: 不存在返回-1。
示例2:
输入：words = [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”,”dad”, “”, “”], s = “ball”
输出：4
提示:
words的长度在[1, 1000000]之间
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sparse-array-search-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

重点总结

1、需要格外注意，字符串数组中存在大量的空字符串，如何解决？

2、字符串比较使用 compareTo() 方法

  1. class Solution {
  2.     public int findString(String[] words, String s) {
  3.         //定义左右边界，使用二分查找
  4.         int left = 0;
  5.         int right = words.length - 1;
  6.         while(left<=right){
  7.             int mid = (left + right)/2;
  8.             //先向右侧查找第一个非空的字符串
  9.             while(mid <= right && "".equals(words[mid])){
  10.                 mid++;
  11.             }
  12.             //mid>right说明右侧字符串全部为空，此时向mid的左侧查找
  13.             if(mid>right){
  14.                 mid = (left + right)/2 - 1;
  15.                 while("".equals(words[mid])&&mid>=left){
  16.                 mid--;
  17.             }
  18.             //mid<left说明左侧也全部为空字符串，直接返回-1
  19.             if(mid<left){
  20.                 return -1;
  21.             }
  22.             }
  23.             //根据字符串的比较结果，重新定义左右边界
  24.             if(words[mid].compareTo(s)==0){
  25.                 return mid;
  26.             }else if(words[mid].compareTo(s)>0){
  27.                 right = mid -1;
  28.             }else{
  29.                 left = mid + 1;
  30.             }  
  31.         }
  32.         return -1;
  33.     }
  34. }

旋转数组的最小数字

https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
示例 1：
输入：[3,4,5,1,2]
输出：1
示例 2：
输入：[2,2,2,0,1]
输出：0
注意：本题与主站 154 题相同：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/

重点总结

1、暴力法并不是最优解

2、二分查找法的一般初始判定 while(left<right)

3、为什么low + (high - low) // 2而不是 (high + low) // 2

  1.   因为low+high在low和high特别大的时候可能会造成溢出，使用减法避免了溢出发生。但是第一种写法也不是     万能的，比如low可以取负数的时候。
class Solution {
    public int minArray(int[] numbers) {
        int left = 0;
        int right = numbers.length -1;
        //基本判定流程
        while(left<right){
            int mid = (left + right)/2;
            //mid<right则mid右边是升序排列的，最小值应该在mid左边
            if(numbers[mid]<numbers[right]){
                right = mid;
            //mid>right则旋转前的前半部分在mid的右边
            }else if(numbers[mid]>numbers[right]){
                left = mid + 1;
            //mid=right，无法判断旋转是怎么发生的，所以暴力向前搜索，确定旋转发生的位置
            }else{
                right -= 1;
            }
        }
        return numbers[left];
    }
}