【手撕代码】二分查找：递归和非递归实现

梦里梦外; 2022-02-16 01:45 194阅读 0赞

本文主要讲述面试现场常遇见的手撕代码题：二分查找。虽然代码很好理解也很简单，但是感觉只有多练，多理解才能真的掌握。千万不要眼高手低，稳扎稳打才是王道。

## 一、非递归版本 ##

public class BinarySearch {
    
        /**
         * 非递归实现
         * @param array ： 有序数组
         * @param key ：需要查找的数
         * @return ：返回 key 在数组 array 中的下标
         */
        public static int binarySearch(int[] array, int key){
            if(array.length < 1){
                return -1;
            }
    
            int mid;
            int start = 0;
            int end = array.length - 1;
    
            while(start <= end){
                // 为了防止int溢出，最好这样写
                mid = (end - start) / 2 + start;
                if(key > array[mid]){
                    start = mid + 1;
                }else if(key < array[mid]){
                    end = mid - 1;
                }else{
                    return mid;   // 找到了
                }
            }
            return -1;   // 没找到
        }
    
        public static void main(String[] args) {
            int[] arr = {1,2,3,4,5};
            System.out.println(binarySearch(arr,3));
        }
    }

--------------------

## 二、递归版本实现 ##

public class BinarySearchWithRecursion {
    
        public static int binarySearch(int[] array, int key){
            if(array.length < 1){
                return -1;
            }
    
            int index = binarySearch(array, key, 0, array.length - 1);
    
            return index;
        }
    
        public static int binarySearch(int[] array, int key, int start, int end){
            int mid = (end - start) / 2 + start;
            // 递归终止条件
            if(array[mid] == key){
                return mid;
            }
    
            if(start >= end){
                return -1;
            }else if(key > array[mid]){
                return binarySearch(array, key, mid + 1, end);
            }else if(key < array[mid]){
                return binarySearch(array, key, start, mid - 1);
            }
            return -1;
        }
    
        public static void main(String[] args) {
            int[] arr = {1,2,3,4,5,6};
            System.out.println(binarySearch(arr, 6));
        }
    }