韩顺平 数据结构与算法 （9

韩顺平 数据结构与算法 （9 二分查找

1. 基本介绍
   1. 二分查找要求是查询一个有序数组
   2. 分递归和非递归查找
2. 查找思路
   1. 首先确定数组中间的下标
      mid = (left+right)/2
   2. 然后让需要查找的数findVal和arr[mid]比较
      1. if(findVal>arr[mid]){说明，要查找的数在mid的右边，因此需要向右递归查找}
      2. if(findVal
      3. if(findVal=arr[mid]){说明，要查找的数就是mid}
   3. 结束递归的条件
      1. 找到时结束递归
      2. 递归完整个数组仍然没有找到findVal，也需要结束递归==>>当left>right，就需要退出
3. 代码演示——

package DataStructures.Search;

import java.util.ArrayList;
import java.util.List;

public class BinarySearch {
    public static void main(String[] args) {

        //二分查找，数组必须是有序的(实例默认从小到大)
        int arr[] = {1, 8, 10, 89, 1000,1000,1000,1000, 1234};
        //int resIndex = binarySearch(arr, 0, arr.length - 1, 11);
        //System.out.println(resIndex);
        //优化后
        List resIndexList = binarySearch2(arr,0,arr.length-1,1000);
        System.out.println("resIndexList="+ resIndexList);
    }

    
    public static int binarySearch(int arr[], int left, int right, int findVal) {
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        if (findVal > midVal) {
            //向右递归
            return binarySearch(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) {
            //想左递归
            return binarySearch(arr, left, mid - 1, findVal);
        } else {
            return mid;
        }
    }
    
    public static List binarySearch2(int arr[], int left, int right, int findVal) {
        if (left > right) {
            return new ArrayList();
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        if (findVal > midVal) {
            //向右递归
            return binarySearch2(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) {
            //想左递归
            return binarySearch2(arr, left, mid - 1, findVal);
        } else {
            List resIndexList = new ArrayList();
            int temp = mid - 1;
            while (true) {
                if (temp < 0 || arr[temp] != findVal) {
                    break;
                }
                resIndexList.add(temp);
                temp -= 1;
            }
            resIndexList.add(mid);
            temp = mid + 1;
            while (true) {
                if (temp > arr.length - 1 || arr[temp] != findVal) {
                    break;
                }
                resIndexList.add(temp);
                temp+=1;
            }
            return resIndexList;
        }
    }
}