二分查找

二分搜索是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

python

#!/usr/bin/python3
def binarySearch(array,l,r,x):
    if r>=l:
        mid =int(l+(r-1)/2)
        if array[mid] ==x:
            return mid
        elif array[mid]>x:
           return  binarySearch(array,l,mid-1,x)
        else:
           return  binarySearch(array,mid+1,r,x)
    else:
        return -1

# 测试数组
arr = [ 2, 3, 4, 10, 40 ]
x = 10

result = binarySearch(arr, 0, len(arr)-1, x)
if result != -1:
    print("元素在数组中的索引为",result)
else:
    print("元素不在数组中")

java

package org.java.base.algorithm;

/**
 * @ClassName BinarySearch
 * @Description TODO
 * @Author liuhaihua
 * @Date 2021/8/5 22:14
 * @Version 1.0
 */
public class BinarySearch {
  public static void main(String[] args) {
     //测试数组
    Integer[] arr ={2,3,4,10,40};
    int x = 10;

    int result = biarysearch(arr, 0, arr.length-1, x);
    if(result != -1) {
      System.out.println("元素在数组中的索引为"+result);
    }else {
      System.out.println("元素不在数组中");
    }


  }

  public  static int biarysearch(Integer[] array,int left,int right,int number){
    if(right>=left){
      int mid = (left+(right-1)/2);
      if(array[mid]==number){
        return mid;
      }else{
        if(array[mid]>number){
          return biarysearch(array,left,mid-1,number);
        }else{
          return biarysearch(array,mid+1,right,number);
        }
      }

    }else {
      return -1;
    }
  }
}