二分法

一、非递归方法:

需要是有序数组
二分法查找的思路如下：

（1）首先，从数组的中间元素开始搜索，如果该元素正好是目标元素，则搜索过程结束，否则执行下一步。

（2）如果目标元素大于/小于中间元素，则在数组大于/小于中间元素的那一半区域查找，然后重复步骤（1）的操作。

（3）如果某一步数组为空，则表示找不到目标元素。

  1. public static int binarySearch(int[] arr,int target)
  2.     {
  3.         int low=0;
  4.         int high=arr.length-1;
  5.         while(low<=high) {
  6.             int mid=(int)Math.floor((low+high)/2);
  7.             System.out.println(mid);
  8.             if(target==arr[mid]) {
  9.                 return mid;
  10.             }else if(target>arr[mid])
  11.             {
  12.                 low=mid+1;
  13.             }else {
  14.                 high=mid-1;
  15.             }
  16.         }
  17.         return -1;
  18.     }

一、递归方法:

int index = Arrays.binarySearch(array, k);Java中含有的搜索函数

  1. public static int binarySearch(int[] arr,int low,int high,int target)
  2.     {
  3.         if(low>high)return -1;
  4.         int mid=Math.round((low+high)/2);
  5.         if(target==arr[mid])
  6.         {
  7.             return mid;
  8.         }else if(target<arr[mid]) {
  9.             high=mid-1;
  10.             return binarySearch(arr,low,high,target);
  11.         }else {
  12.             low=mid+1;
  13.             return binarySearch(arr,low,high,target);
  14.         } 
  15.     }