数组查找

1. 顺序查找
   从无序数组第一个元素开始逐个元素进行比较，若某个元素与目标元素相等则查找成功，否则直至最后一个元素都不等则查找失败。

2. 二分查找
   在有序数组中先确定目标元素所在的区间，然后逐步缩小查找范围，直到找到或找不到目标元素。

   int binarySearch(int[] nums, int tar) {
       int low = 0, high=nums.length;
       while(low<=high) {
           int mid = low+(high-low)/2;
           if(nums[mid]==cur)     return mid;
           else if(nums[mid]>cur) high = mid - 1;
           else                   low  = mid + 1;
       }
       return -1;
   }
   

3. 二分查找扩展
   1) 在一个有重复元素的数组中查找元素的最左位置。
   需要判断返回值 low: 若该位置元素等于目标元素则 low 是最左位置，否则 low 是目标元素的插入位置。

   int binarySearch(int[] nums, int target) {
      int low=0, high=nums.length-1;
      while(low<high) {
          int mid=low+(high-low)/2;
          if(target<=nums[mid]) high=mid;
          else                  low =mid-1;
      }
      return low;
   }

   2) 在一个有重复元素的数组中查找元素的最右位置
   需要判断返回值 low: 若该位置元素等于目标元素则 low 是最左位置，否则 low+1 是目标元素的插入位置。

    int binarySearchRight(int[] nums, int target) {
        int low=0, high=nums.length-1;
        while(low<high) {
            int mid=low+(high-low)/2;
            if(target>=nums[mid]) low =mid;
            else                  high=mid-1;
        }
        return low;
    }

   3) 二维数组中查找元素
   在从左到右、从上到下递增的二维数组中查找一个元素：从右上角的元素开始比较，大于target则行+1,否则列-1

   boolean find(int[][] nums, int target) {
       if(nums==null || nums.length==0 || nums[0].length==0) {
           return false;
       }
       int row=0, col=nums[0].length-1;
       while(row<nums.length && col>=0) {
           if(nums[row][col]==target) {
               return true;
           } else if(nums[row][col]<target) {
               row++;
           } else {
               col--;
           }
       }
       return false;
   }