[游戏开发]二分查找的基本思想及实现

要求在有序数组中进行二分查找，不是有序，则要先排序
思路：
1.首先确定该数组的中间的下标
mid=（left+right）/2;
2.然后让需要查找的数findvalue和arr[mid]比较
3.findvalue>arr[mid],说明该数在mid的右边，因此需要递归向右查找
4.findvalue<arr[mid],说明你要查找的数在mid的左边，因此需要递归向左查找
5.findvalue=arr[mid],找到返回
6.当left大于right，说明没找到，返回-1；

在返回的时候还有一个问题，就是如果找到数在数组中有多个，就需要返回多个坐标。

  public static ArrayList<Integer> binarysearch(int[] arr,int left,int right,int findvalue) {
        if (left >=right) {//如果没有=号的话就会导致数组索引越界java.lang.ArrayIndexOutOfBoundsException: 8
            return new ArrayList<Integer>();
        }
        int mid = (left + right) / 2;//中间位置的坐标

        if (findvalue > arr[mid]) {//向右递归
            return binarysearch(arr, mid + 1, right, findvalue);
        } else if (findvalue < arr[mid]) {//向左递归
           return binarysearch(arr, left, mid - 1, findvalue);
        } else {
            //找到之后，往两边去找到相等值的坐标,比如[1,2,5,100,100,100,452,520]，这个数组中有查找的是100，那么100有三个坐标，分别是3,4,5；这时就需要下面的操作进行查找了
            ArrayList<Integer> arrayList=new ArrayList<Integer>();
            int temp=mid-1;
            while (true){
                if(temp<0||arr[temp]!=findvalue){//向左边找，有不同的就退出，或则没找到
                    break;
                }
                arrayList.add(temp);
                temp--;
            }
            arrayList.add(mid);//中间那个找到的值，先加入
            temp=mid+1;
            while (true){
                if(temp>right||arr[temp]!=findvalue){//向右递归，有不同的就退出，或则没找到
                    break;
                }
                arrayList.add(temp);
                    temp++;
            }
            return arrayList;//返回坐标集合
        }
    }