Java二分查找

前提

待查找数组必须为有序数组（可以是升序也可以是降序）

本次谈论为升序初级二分查找

基础版

“>>>”用位移操作可避免出现负数和int显示有误的情况

 //这只能找到第一个等于target的值的下标，且数组中必须有target，数组要求为升序
    public static int binarySearch(int[] arr,int target){
        int left = 0;
        int right = arr.length - 1;
        while(left <= right){
            int mid = (left + right)>>>1;
            if(arr[mid] == target){
                return mid;
            }else if(arr[mid] < target){
                left = mid + 1;
            }else if(arr[mid] > target){
                right = mid - 1;
            }
        }
        return -1;
    }

这里的右指针是数组最后一个元素，则while判断可以有等号，且判断移动后right = mid - 1 

改进版

public static int binarySearchNews(int[] arr,int target){
        int left = 0;
        int right = arr.length;
        while(left < right){
            int mid = (left + right)>>>1;
            if(arr[mid] == target){
                return mid;
            }else if(arr[mid] < target){
                left = mid + 1;
            }else if(arr[mid] > target){
                right = mid;
            }
        }
        return -1;
    }

这里的右指针是数组最后一个元素再往后一个位置，相当于是边界，则while判断不能有等号，且判断移动后right = mid 。推荐使用这种方式，减少执行和判断次数。

平衡版

类似“夹逼准则“，再while循环内，i和j依次循环逼近目标值，最后在循环外运用三目运算符比较。

class Solution {
    public int search(int[] nums, int target) {
     int i = 0;
     int j = nums.length;
     while(i+1
         int m = (i+j)>>>1;
         if(nums[m]>target){
             j = m;
         }else {     
             //target>=nums[m]的情况，且最后利用的是i下表所在值
             i = m;
         }
     }
     return (nums[i] == target) ? i : -1;
    }
}

（搜索插入位置）Java中Arrarys工具类提供的binarySearch实现的返回值

// Like public version, but without range checks.
    private static int binarySearch0(long[] a, int fromIndex, int toIndex,
                                     long key) {
        int low = fromIndex;
        int high = toIndex - 1;
 
        while (low <= high) {
            int mid = (low + high) >>> 1;
            long midVal = a[mid];
 
            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

若找不到则返回一个负数，同时返回的应含有搜索目标插入点的位置信息，所以返回的-(low + 1) = -(插入点 + 1），因为插入点为数组下标是正数，所以要加个负号，又因为插入点可能在0处，所以要加个1才能保证找不到的时候返回负数。

Leftmost/Rightmost实现（可有重复元素）

 public int leftMost(int[] arr , int target){
     int i = 0;int j = arr.length - 1;
     int candicate = -1;
     while(i<=j){
         int m = (i + j)>>>1;
         if(target
            j = m - 1; 
         }else if(target>arr[m]){
             i = m + 1;
         }else{
            candicate = m;
            j = m - 1;   //有可能是重复元素，j则继续往左边走一位，继续判断进不进入循环
         }
     }
     return candicate;
    }

public int rightMost(int[] arr , int target){
     int i = 0;int j = arr.length-1;
     int candicate = -1;
     while(i<=j){
         int m = (i + j)>>>1;
         if(target
            j = m - 1; 
         }else if(target>arr[m]){
             i = m + 1;
         }else{
            candicate = m;
            i = m + 1;    //有可能是重复元素，i则继续往右边走一位，继续判断进不进入循环
         }
     }
     return candicate;
    }

Leftmost/Rightmost应用

Leftmost（返回目标元素最靠左的下标）：返回值加一求排名，返回值减一求目标值小于目标值的范围，返回值求大于等于目标值的范围和目标值不存在时的插入位置。

Rightmost（返回目标元素最靠右的下标）：返回值加一求大于目标值的范围，返回值求小于等于目标值的范围。

综合起来用即可求出一个区间的确定范围。

-----笔记整理来自黑马程序员-----