Java中的二进制搜索
二进制搜索用于从多个元素中搜索关键元素。二进制搜索比线性搜索快。
对于二进制搜索，数组元素必须按升序排列。如果您有未排序的数组，则可以使用
Arrays.sort(arr)方法对数组进行排序。
算法:
第1步: 遍历数组
第2步: 将关键元素与数组元素匹配
第3步: 如果找到关键元素，则返回数组元素的索引位置
第4步: 如果找不到关键元素，则返回-1
Java中的二进制搜索示例
让我们看一下Java中的二进制搜索示例。
class BinarySearchExample{
public static void binarySearch(int arr[], int first, int last, int key){
int mid = (first + last)/2;
while( first <= last ){
if ( arr[mid] < key ){
first = mid + 1;
}
else if ( arr[mid] == key ){
System.out.println("Element is found at index: " + mid);
break;
}
else{
last = mid - 1;
}
mid = (first + last)/2;
}
if ( first > last ){
System.out.println("Element is not found!");
}
}
public static void main(String args[]){
int arr[] = {
10,20,30,40,50}
;
int key = 30;
int last=arr.length-1;
binarySearch(arr,0,last,key);
}
}
输出:
Element is found at index: 2
使用递归的Java中的二进制搜索示例
让我们看一下Java中的二进制搜索的示例，在该示例中，我们将使用递归从数组中搜索元素。
class BinarySearchExample1{
public static int binarySearch(int arr[], int first, int last, int key){
if (last>=first){
int mid = first + (last - first)/2;
if (arr[mid] == key){
return mid;
}
if (arr[mid] > key){
return binarySearch(arr, first, mid-1, key);
//search in left subarray }
else{
return binarySearch(arr, mid+1, last, key);
//search in right subarray }
}
return -1;
}
public static void main(String args[]){
int arr[] = {
10,20,30,40,50}
;
int key = 30;
int last=arr.length-1;
int result = binarySearch(arr,0,last,key);
if (result == -1) System.out.println("Element is not found!");
else System.out.println("Element is found at index: "+result);
}
}
输出:
Element is found at index: 2
使用Arrays.binarySearch()在Java中进行二进制搜索的示例
import java.util.Arrays;
class BinarySearchExample2{
public static void main(String args[]){
int arr[] = {
10,20,30,40,50}
;
int key = 30;
int result = Arrays.binarySearch(arr,key);
if (result < 0) System.out.println("Element is not found!");
else System.out.println("Element is found at index: "+result);
}
}
输出:
Element is found at index: 2
