JAVA Python 二分查找

二分查找：也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列

首先，假设表中元素是按升序排列，将表中间位置记录的​​关键字​​​与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置​​记录​​​将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的​​记录​​，使查找成功，或直到子表不存在为止，此时查找不成功。

1.必须采用​​顺序存储结构​​。

2.必须按关键字大小有序排列。

解题步骤：

1.定义3个用来记录索引值的变量，变量min记录当前范围最小索引值，初始值为0；变量Max记录当前范围最大索引值，初始值为数组长度-1；变量mid记录当前范围最中间元素的索引值，初始值为（min+max)/2

2.使用循环，判断当前范围下，最中间元素值与指定查找的数值是否相等

   ?若相等，结束循环，返回当前范围最中间元素的索引值mid

   ?若不相等，根据比较结果，缩小查询范围为上一次查询范围的一半

                ✳中间元素值比要查询的的数值大，说明要查询的数值在当前范围的最小索引位置与中间索引位置之间，此时，更新查询范围为：

              范围最大索引值=上一次中间索引位置-1

               ✳中间元素比查询的数值小，说明要查询的数值在当前范围的最大索引位置与中间索引位置之间，此时，更新查询范围为：           

                范围最小索引值=上一次中间索引位置+1

                ✳在新的查询范围中，更新中间元素值的位置，再次使用最中间元素值与指定查找的数值是否相等。

                  中间索引值=（范围最小索引值+范围最大索引值）/2

3.每次查询范围缩小一半后，使用if语句判断，查询范围是否小于0个元素，若小于0个元素，则说明指定数值没有查询到，返回索引值-1.

list=list(range(10))
def bin_search(data_set,val):
    min=0
    max=len(data_set)-1
    while min<=max:#只有当min<max的时候证明中间有数
        mid=(max+min)//2
        if data_set[mid]==val:
            return mid
        elif data_set[mid]>val:
            max=mid-1
        else:
            min=mid+1
    return -1
if __name__ == '__main__':
    print(bin_search(list,7))      

public class erFen {
  public static void main(String[] args) {
    int[] arr = {1,2,3,4,5,6,7,8,9};
    int num=halfSearch(arr, 2);
    System.out.println(num);
    
  }
  public static int halfSearch(int[] arr,int number) {
    //定义3个变量，用来记录Min，max,mid的位置
    int min =0;
    int max=arr.length-1;
    int mid = (min+max)/2;
    //判断Mid位置上的原始与number的值是否相同
    while (arr[mid] != number) {
      //没找到，更新范围，继续比较
      //更新范围
      if (arr[mid]>number) {
        //在左边
        max=mid-1;
      } else {
        //在右边
        min = mid +1;
      }
      //使用If语句判断，查询范围是否小于0个元素
      if ((max-min)<0) {
        //没有找到
        return -1;
      }
      //更新Mid值
      mid=(min+mid)/2;
    }
    //找到了，返回Mid的位置
    return mid;
  }
  

}