二分查找

题目

查找数组中值为1000的索引，[3,5,7,1000,1000,9999]

一、递归实现二分查找

前提：数组必须有序

时间复杂度：O(log₂n)

思路：先对比待查找的值和数组中间值，如果待查找值较大，则在继续中间值的右边查找；如果待查找的值较小，则在中间值的左边查找，以此递归。

package search;

import java.util.ArrayList;
import java.util.Arrays;

public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {3,5,7,100,100,100,999};

        ArrayList binary = binary(arr, 0, arr.length, 8);

        System.out.println(binary);
    }

    public static ArrayList binary(int[] arr,int left,int right,int val){

        //没有查找到对应的数据
        if (left > right){

            return null;
        }

        int mid = (left + right)/2;
        ArrayList<Integer> list = new ArrayList<Integer>();
        //比较当前值和中间值
        if (val > arr[mid]){
            list = binary(arr, mid+1, right, val);
        }else if (val < arr[mid]){
            list = binary(arr, left, mid-1, val);
        }else{
            int temp = mid-1;
            //查找到对应的数据，但需查找到该数据的全部索引
            while(true){
                if (left < 0 || temp < 0 || arr[temp]!=val){
                    break;
                }

                list.add(temp);
                temp--;
            }

            list.add(mid);

            temp = mid+1;
            //查找到对应的数据，但需查找到该数据的全部索引
            while(true){
                if (right > arr.length || temp >= arr.length || arr[temp]!=val){
                    break;
                }

                list.add(temp);
                temp++;
            }


        }

        return list;
    }
}

二、非递归实现二分查找

//非递归实现二分查找
    public static int binary2(int[] arr ,int val){
        int left = 0;
        int right = arr.length - 1;
        int mid = 0;

        while(left <= right){
            mid = (left + right)/2;
            if (val == arr[mid]){
                return mid;
            }
            if (val > arr[mid]){
                left = mid + 1;
            }
            if (val < arr[mid]){
                right = mid - 1;
            }

        }
        return -1;

    }