圖解Java經典算法折半查找的原理與實現(xiàn)
二分查找
二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法，可以在數(shù)據(jù)規(guī)模的對數(shù)時間復雜度內完成查找。是一種在有序數(shù)組中查找某一特定元素的搜索算法。
算法思路
以升序數(shù)列為例，比較目標元素與數(shù)列中間位置的元素的大小，如果目標元素比中間位置的元素大，則繼續(xù)在數(shù)列的后半部分中進行二分查找；如果目標元素比中間位置的元素小，則在數(shù)列的前半部分進行比較；如果相等，則找到了元素的位置。每次比較的數(shù)列長度都會是之前數(shù)列的一半，直到找到相等元素的位置或者最終沒有找到目標元素。
圖解
給定一個有序的升序排列的數(shù)組 nums=[-1，0，2，5，8，12，18，38，43，46]
然后在該數(shù)組中找到目標值 target = 12。
圖解如下：
力扣原題
題目描述：
給定一個 n 個元素有序的（升序）整型數(shù)組 nums 和一個目標值 target ，寫一個函數(shù)搜索 nums 中的 target，如果目標值存在返回下標，否則返回 -1。
示例 1:
輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現(xiàn)在 nums 中并且下標為 4
示例 2:
輸入: nums = [-1,0,3,5,9,12], target = 2
輸出: -1
解釋: 2 不存在 nums 中因此返回 -1
解題思路：
根據(jù)題意得出該數(shù)組為有序數(shù)組，這也是使用二分查找的前提條件。
- 定義兩個指針分別指向數(shù)組的首尾兩個元素；
- 找到數(shù)組的中間值mid；
- 如果
nums[mid] < target，則 target 位于數(shù)組的后半部分，反之nums[mid] > target在前半部分； - 重復上一步操作，直到
nums[mid] = target，說明找到target，返回下標即可。
Java代碼實現(xiàn)：
class Solution {
public int search(int[] nums, int target) {
int left = 0,right = nums.length - 1;
while(left <= right) { // 循環(huán)條件
int mid = left + (right - left) / 2;
if(nums[mid] == target){
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 找不到則返回-1
}
}
復雜度分析：
- 時間復雜度：O(logn)，其中 n 是數(shù)組的長度。
- 空間復雜度：O(1)。
到此這篇關于圖解Java經典算法折半查找的原理與實現(xiàn)的文章就介紹到這了,更多相關Java折半查找內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
DeepSeek作為一款強大的代碼搜索和分析工具,能夠幫助開發(fā)者快速定位代碼、理解項目結構以及優(yōu)化代碼質量,本文將詳細介紹如何在IntelliJ?IDEA中集成DeepSeek,并展示如何利用它來提升開發(fā)效率,感興趣的朋友一起看看吧2025-02-02
將java程序打成jar包在cmd命令行下執(zhí)行的方法
這篇文章主要給大家介紹了關于將java程序打成jar包在cmd命令行下執(zhí)行的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧。2018-01-01
視圖解析其實就是SpringBoot某一個controller的方法執(zhí)行完成之后，它是跳轉到那個頁面。由于我們springboot項目默認打包為jar包，是形成壓縮包的形式，而jsp又不支持壓縮，所以我們SpringBoot不知JSP的，需要引入第三方模板引擎才可以處理2022-10-10
這篇文章主要介紹了Java使用Redis的方法,接合實例形式分析了相關redis驅動包安裝、java連接redis服務器、數(shù)據(jù)存儲、讀取等相關操作技巧,需要的朋友可以參考下2018-05-05
攜程Apollo（阿波羅）安裝部署以及java整合實現(xiàn)
這篇文章主要介紹了攜程Apollo（阿波羅）安裝部署以及java整合實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-08-08
Java中的functor實現(xiàn)...2006-12-12
Java語言的輸入輸出功能是十分強大而靈活的,下面這篇文章主要給大家介紹了關于Java中文件的操作與輸入輸出流的相關資料,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2023-12-12
在SpringBoot項目中,通過在application.properties文件中添加配置項,然后使用@ConfigurationProperties注解將這些配置項與實體Bean進行綁定,可以實現(xiàn)配置項與實體類字段的自動關聯(lián),進而方便地讀取配置文件中的數(shù)據(jù),這種方法不僅簡化了配置管理2024-11-11
三目運算符是我們經常在代碼中使用的,這篇文章主要給大家介紹了關于Java三目運算符用法的相關資料,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2023-11-11
Spring Boot security 默認攔截靜態(tài)資源的解決方法
這篇文章主要介紹了Spring Boot security 默認攔截靜態(tài)資源,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-03-03