大飞

关注TA

挑战一切！

世界的顶端
混口饭吃
写了333,609字

该文章投稿至Nemo社区 Python 板块复制链接

Python 二分查找算法

发布于 2018/09/21 00:48 1,598浏览 0回复 2,558字

"""
 递归二分查找算法 将排序好的数组（比如从小到大）或队列一分二为，选取中间值比较
 如果要查找的数值比中间值大，说明要查找的数值在前半部分，相反在后半部分，继续将
 前半部分（或后半部分）一分为二，如此循环，直到找出中间值为索要寻找的数值
"""
numberArray = [1, 3, 5, 7, 9, 11, 13]


def binary_search(array, search_data, start_index, end_index):
    # python 整数相除如果有小数点会返回浮点型，这个跟Java不同
    mid_index = int((start_index + end_index) / 2)
    # 如果查找的数据不存在返回-1
    if search_data < array[start_index] or search_data > array[end_index] or start_index > end_index:
        return -1
    # 查找的数据在后半部分
    if search_data > array[mid_index]:
        return binary_search(array, search_data, mid_index + 1, end_index)
    # 查找到数据在前半部分
    elif search_data < array[mid_index]:
        return binary_search(array, search_data, start_index, mid_index - 1)
    # 最终索引
    else:
        return mid_index


print(binary_search(numberArray, 3, 0, len(numberArray) - 1))
print(binary_search(numberArray, 11, 0, len(numberArray) - 1))
print(binary_search(numberArray, 7, 0, len(numberArray) - 1))
print(binary_search(numberArray, 4, 0, len(numberArray) - 1))

package com.hangzhou.servicezuul;

/**
 * 二分查找又称折半查找，它是一种效率较高的查找方法。
 * 　　【二分查找要求】：1.必须采用顺序存储结构 2.必须按关键字大小有序排列。
 */
public class BinarySearch {
   public static void main(String[] arg) {
      int[] numberArray = new int[]{1, 3, 5, 7, 9, 11, 13};
      System.out.println(binarySearch(numberArray, 3, 0, numberArray.length - 1));
      System.out.println(binarySearch(numberArray, 11, 0, numberArray.length - 1));
      System.out.println(binarySearch(numberArray, 7, 0, numberArray.length - 1));
      System.out.println(binarySearch(numberArray, 6, 0, numberArray.length - 1));


   }

   /**
    * 递归二分查找算法
    * @return 索引
    */
   public static int binarySearch(int[] array, int searchData, int startIndex, int endIndex) {
      int midIndex = (startIndex + endIndex) / 2;
      // 查找的数据不存在
      if (searchData < array[startIndex] || searchData > array[endIndex] || startIndex > endIndex) {
         return -1;
      }
      // 查找的数据在后半部分
      if (searchData > array[midIndex]) {
         return binarySearch(array, searchData, midIndex + 1, endIndex);
         // 查找的数据在前半部分
      } else if (searchData < array[midIndex]) {
         return binarySearch(array, searchData, startIndex, midIndex - 1);
      } else {
         return midIndex;
      }
   }
}

执行结果如下:

/Users/lyf/PycharmProjects/venv/bin/python /Users/lyf/PycharmProjects/TCPChatDemo/BinarySearch.py

-1

Process finished with exit code 0

点了个评