majianyu
4/8/2018 - 7:10 AM

## binary_search

``````package com.test;

public class BinarySearch {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
System.out.println(binarySearch(arr, 9));
}

private static int binarySearch(int[] arr, int key) {
int lo = 0;
int hi = arr.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (key < arr[mid]) {
hi = mid - 1;
} else if (key > arr[mid]) {
lo = mid + 1;
} else {
return mid;
}
}
return -1;
}
private static int binarySearch2(int[] arr,int key,int lo,int hi,int level) {
// 递归实现
// 打印递归深度
for (int i = 0;i< level;i++) {
System.out.print("    ");
}
System.out.printf("lo:%d hi:%d level:%d\n",lo,hi,level);

if (lo > hi) {
return -1;
}
int mid = lo+(hi - lo) / 2;
if (key < arr[mid] ){
return binarySearch2(arr,key,lo,mid - 1,++level);
} else if (key > arr[mid]) {
return binarySearch2(arr,key,mid + 1,hi,++level);
} else {
return mid;
}
}
}``````
``````def binary_search(arr: list, key: int) -> int:
lo = 0
hi = len(arr) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if key < arr[mid]:
hi = mid - 1
elif key > arr[mid]:
lo = mid + 1
else:
return mid
return -1

def binary_search2(arr: list, key: int, lo: int, hi: int, level: int) ->int:
# 递归实现
# 打印递归深度
print("{:s}lo:{:d} hi:{:d} level:{:d}".format("    " * level, lo, hi, level))

if lo > hi:
return -1
mid = lo + (hi - lo) // 2
if key < arr[mid]:
return binary_search2(arr, key, lo, mid - 1, level + 1)
elif key > arr[mid]:
return binary_search2(arr, key, mid + 1, hi, level + 1)
else:
return mid

if __name__ == '__main__':
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(binary_search2(arr, 9, 0, len(arr)-1, 0))
``````
``````package main

import "fmt"

func main() {
arr := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
fmt.Println(BinarySearch2(arr, 9, 0, len(arr)-1, 0))
}
func BinarySearch(arr []int, key int) (int) {
lo := 0
hi := len(arr) - 1
for lo <= hi {
mid := lo + (hi-lo)/2
if key < arr[mid] {
hi = mid - 1
} else if key > arr[mid] {
lo = mid + 1
} else {
return mid
}
}
return -1
}
func BinarySearch2(arr []int, key, lo, hi, level int) int {
// 递归实现
// 打印递归深度
for i := 0; i < level; i++ {
fmt.Print("    ")
}
fmt.Printf("lo:%d hi:%d level:%d\n", lo, hi, level)

if lo > hi {
return -1
}
mid := lo + (hi-lo)/2
if key < arr[mid] {
return BinarySearch2(arr, key, lo, mid-1, level+1)
} else if key > arr[mid] {
return BinarySearch2(arr, key, mid+1, hi, level+1)
} else {
return mid
}

}
``````