二分查找算法思想
二分查找针对的是一个有序的数据集合也就是数组（这也成为了二分查找的一个重要局限性），查找思想有点类似分治思想。
每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为0
（一：返回查找数对应的下标）
java代码实现第一种递归版：
public class BinarySearch {
public static void main(String[] args) {
int arr[]={1,2,3,4,5,6,7,8,9,10};
int index=BinarySearch(arr,0,arr.length,2);
System.out.println("查找的位置"+rIndex);
}
/**
int arr[]:已经排好序的数组
int left：左下标
int right ：右下标
int findVal ：要找的值
*/
public static int BinarySearch(int arr[],int left,int right,int findVal){
//找到中间位置
int mid=(left+right)/2;
//找到中间下标在数组中对应的值
int midVal=arr[mid];
//进行判断，如果左边下标大于右边下标，表示已经遍历完数组,没有找到该元素，返回-1；
if(left>right){
return -1;
}
//如果要找的元素findVal大于中间值midVal，则在数组的右边，向右进行递归，
if(midVal<findVal){
return BinarySearch(arr,mid+1,right,findVal);
}else if(midVal>findVal){
//如果要找的元素findVal小于中间值midVal，则在数组的左边，向左进行递归；
return BinarySearch(arr,left,mid-1,findVal);
}else{
//说明找到了该元素，返回该元素对应的下标mid；
return mid;
}
}
}
java代码实现第二种非递归版：
public class BinarySearch {
public static void main(String[] args) {
int arr[]={1,2,3,4,5,6,7,8,9,10};
int index=BinarySearch(arr,0,arr.length,2);
System.out.println("查找的位置"+rIndex);
}
public static int BinarySearch(int arr[],int left,int right，int findVal){
int mid=(left+right)/2;
int midVal=arr[mid];
//先进行判断，如果要找的元素findVal小于数组的最小值或者大于数组的最大值，则不能找到findVal，返
//回-1
//如果左边下标大于右边下标也不能找到该元素findVal,返回-1
if(findVal<arr[left]||findVal>arr[right]||left>right){
return -1;
}
//左下标<右下标，说明数组还没有遍历完
while(left<right){
//因为左右下标会变，需要更新mid值
mid=(left+right)/2;
//如果，要找的值findVal 大于arr[mid],在数组的右边，左下标定义为left=mid+1
if(findVal>arr[mid]){
left=mid+1;
}else if(findVal<arr[mid]){
//如果要找的元素findVal小于arr[mid]，说明在数组的左边，右下边冲洗定义为right=mid-1
right=mid-1;
}else{
return mid;
}
//遍历完数组没有找到挂元素findVal，返回-1；
return -1;
}
}
（二：返回一个集合，为全部该数值的下标）
public class BinarySearch {
public static void main(String[] args) {
int []arr={1,2,2,2,2,6,7,8,9,10};
List<Integer> resIndexList= BinarySearch2(arr,0,arr.length,2);
System.out.println("查找的位置"+resIndexList);
}
/**
int arr[]:排好序的数组
int left：左边下标
int right：右边索引
int findVal：要找的元素
return：返回一个集合，为全部该数值的下标
*/
public static List<Integer> BinarySearch(int arr[],int left,int right,int findVal){
//中间下标
int mid=(left+right)/2;
int midVal=arr[mid];
//如果左索引大于右索引，返回一个空链表
if(left>right){
return new ArrayList<Integer>();
}
//如果要找的元素findVal大于中间值midVal，则在数组的右边,向右进行递归
if(midVal<findVal){
return BinarySearch(arr,mid+1,right,findVal);
}else if(midVal>findVal){
//如果要找的元素findVal小于中间值midVal，则在数组的左边，向左进行递归
return BinarySearch(arr,left,mid-1,findVal);
}else{
//创建一个链表
List<Integer> list=new ArrayList();
//定义一个在中间下表前前一个下标temp
int temp=mid-1；
while(true){
//判断，如果下标小于0或者不等于要找的元素findVal，则退出循环，
if(temp<0||arr[temp]!=findVal){
break;
}
//说明下标temp对应数组的值都等于findVal，加入链表
list.add(temp);
temp--;
}
//注意 ：这里不要忘记加入mid
list。add(mid);
//重新定义temp为mid后一个下标
temp=mid+1;
while(true){
if(temp>right||arr[temp]!=findVal){
break;
}
list.add(temp);
temp++;
}
}
//返回链表
return list;
}
}
