Java二分查找算法實(shí)現(xiàn)代碼實(shí)例
這篇文章主要介紹了Java二分查找算法實(shí)現(xiàn)代碼實(shí)例,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
二分查找:
兩種方式: 非遞歸方式和遞歸方式
主要思路: 對(duì)于已排序的數(shù)組(先假定是從小到大排序), 先定義兩個(gè)"指針", 一個(gè)"指向"首元素low, 一個(gè)"指向"末尾元素high. 然后, 開(kāi)始折半比較, 即讓要查找的數(shù)與數(shù)組中間的元素(索引為 low+high/2)比較. 若要查找的數(shù)比中間數(shù)小, 說(shuō)明要查找的數(shù)在數(shù)組左側(cè)(注意前提是數(shù)組從小到大排序), 否則說(shuō)明該數(shù)在數(shù)組的右側(cè). 如果low最后還比high大,倆"指針"交叉了, 說(shuō)明沒(méi)有找到該數(shù), 即數(shù)組不存在該數(shù).
注意事項(xiàng): 排序規(guī)則與數(shù)組的排序順序有關(guān), 即從大到小排序和從小到大排序是不一樣的!!!
代碼如下
class BinarySearch {
// 二分查找非遞歸方式
// arr 給定已排序數(shù)組
// num 要查找的數(shù)
public static int search(int[] arr, int num) {
int low = 0;
int high = arr.length - 1;
int mid = 0;
while (low <= high) {
mid = (low + high) / 2;
if (num < arr[mid]) {
high = mid - 1;
}
if (num > arr[mid]) {
low = mid + 1;
}
if (num == arr[mid]) {
return mid;
}
}
return -1; // 沒(méi)找到
}
// 二分查找遞歸方式
// arr 給定已排序數(shù)組
// num 要查找的數(shù)
// low 初始左側(cè)指針 指向第一個(gè)元素
// high 初始末尾指針 指向最后一個(gè)元素
public static int binarySearch(int[] arr, int num, int low, int high) {
int mid = (low + high) / 2;
// 遞歸結(jié)束條件
if (low > high) {
return -1;
}
if (num < arr[mid]) {
return binarySearch(arr, num, low, mid - 1);
} else if (num == arr[mid]) {
return mid;
} else {
return binarySearch(arr, num, mid + 1, high);
}
}
public static void main(String[] args) {
// 給定數(shù)組 從小到大排序.
int[] arr = {2, 3, 5, 7, 8, 9, 11, 12, 15};
// int[] arr = {15, 12, 11, 9, 8, 7, 5, 3, 2};
int m = 3;
// int index = search(arr, m);
int index = binarySearch(arr, m, 0, arr.length - 1);
System.out.println(index);
}
}
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
Java操作mongodb增刪改查的基本操作實(shí)戰(zhàn)指南
MongoDB是一個(gè)基于分布式文件存儲(chǔ)的數(shù)據(jù)庫(kù),由c++語(yǔ)言編寫(xiě),旨在為WEB應(yīng)用提供可擴(kuò)展的高性能數(shù)據(jù)存儲(chǔ)解決方案,下面這篇文章主要給大家介紹了關(guān)于Java操作mongodb增刪改查的基本操作實(shí)戰(zhàn)指南,需要的朋友可以參考下2023-05-05
java實(shí)現(xiàn)往hive 的map類型字段寫(xiě)數(shù)據(jù)
這篇文章主要介紹了java實(shí)現(xiàn)往hive 的map類型字段寫(xiě)數(shù)據(jù)操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-07-07
這篇文章主要為大家詳細(xì)介紹了Java如何實(shí)現(xiàn)批量下載文件,并以壓縮輸出流的形式返回前端,文中的示例代碼講解詳細(xì),需要的小伙伴可以參考一下2023-10-10
@Async導(dǎo)致controller?404及失效原因解決分析
這篇文章主要為大家介紹了@Async導(dǎo)致controller?404失效問(wèn)題解決，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-07-07
今天帶大家學(xué)習(xí)Java的基礎(chǔ)知識(shí),文中對(duì)Java反射創(chuàng)建對(duì)象作了非常詳細(xì)的介紹及代碼示例,對(duì)正在學(xué)習(xí)Java的小伙伴們很有幫助,需要的朋友可以參考下2021-05-05
Java使用HttpClient實(shí)現(xiàn)文件下載
這篇文章主要為大家詳細(xì)介紹了Java使用HttpClient實(shí)現(xiàn)文件下載，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-08-08
springboot3.0整合mybatis-flex實(shí)現(xiàn)逆向工程的示例代碼
逆向工程先創(chuàng)建數(shù)據(jù)庫(kù)表,由框架負(fù)責(zé)根據(jù)數(shù)據(jù)庫(kù)表,自動(dòng)生成mybatis所要執(zhí)行的代碼,本文就來(lái)介紹一下springboot mybatis-flex逆向工程,感興趣的可以了解一下2024-06-06
SpringBoot定時(shí)調(diào)度之Timer與Quartz詳解
Java?中常用的定時(shí)調(diào)度框架有以下幾種：Timer、ScheduledExecutorService、Spring?Task和Quartz，本文主要來(lái)和大家講講他們的具體使用，需要的可以參考一下2023-06-06
詳解java實(shí)現(xiàn)HTTP請(qǐng)求的三種方式
這篇文章主要介紹了java實(shí)現(xiàn)HTTP請(qǐng)求的三種方式，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-04-04
Java8最新引入函數(shù)式編程概念，該項(xiàng)技術(shù)可以大大提升編碼效率，本文會(huì)對(duì)涉及的對(duì)象等進(jìn)行兩種方法的對(duì)比，對(duì)新技術(shù)更直白的看到變化，更方便學(xué)習(xí)2021-06-06