目錄
一.定義
二.分類
三.線性查找
原理：
思路分析
代碼實現
例題實踐
1.兩數之和
方法一：暴力窮舉法
思路分析
代碼實現
方法二：創建哈希表
思路分析
代碼實現
2.移動零
思路分析
代碼實現
四.二分查找
原理：
思路分析
例題實踐
思路分析
代碼實現
一.定義
查找算法是在數據集合中尋找滿足某種條件的數據元素的過程。
二.分類
在Java中我們常見的查找算法有四種：
1.順序（線性）查找
2.二分查找/折半查找
3.插值查找
4.斐波拉契查找
今天我們講前兩個查找算法
三.線性查找
原理：
線性查找是一種簡單的查找算法，它從數據結構的一端開始，逐個檢查每個元素，直到找到所需的元素或搜索到數據結構的另一端。
思路分析
1.從第一個元素開始，逐個與要查找的元素進行比較；如果當前元素不是要查找的元素，則繼續向后查找；
2.如果找到要查找的元素，則返回該元素的位置；如果查找到數據結構的末端仍未找到要查找的元素，則返回一個標識（如-1），表示查找失敗。
代碼實現
public class LookupAlgorithm
{//線性查找方法public static int linearSearch(int[] arr, int key){//循環遍歷數組，找到要查找的值for(int i = 0; i < arr.length; i++){if(arr[i] == key){return i;}}return -1;//找不到返回-1}public static void main (String[] args){int[] arr = {5,6,9,8,6,11,7,56,89};//現在查找56這個元素int index=linearSearch(arr,56);if(index == -1){System.out.println("未找到該元素");}else{System.out.println("該元素的下標為："+index);}}
}
例題實踐
?
1.兩數之和
給定一個整數數組?nums?和一個整數目標值?target，請你在該數組中找出?和為目標值?target? 的那?兩個?整數，并返回它們的數組下標。你可以假設每種輸入只會對應一個答案，并且你不能使用兩次相同的元素。你可以按任意順序返回答案。
方法一：暴力窮舉法
思路分析
我們可以直接使用嵌套循環，外循環從第一個索引開始，內循環外循環開始的索引處+1開始，一直循環到找出目標值的兩個整數
代碼實現
//暴力窮舉public static int[] TwoValue(int[] arr, int key){//先定義一個數組，來存儲找到的兩個值的索引int[] result=new int[2];//開始遍歷外循環中的每個元素for(int i = 0; i < arr.length; i++){//內循環從外循環的i位置處的下一個開始遍歷for(int j = i+1; j < arr.length; j++){if(arr[i] +arr[j]==key){result[0]=i;result[1]=j;return result;}}}return result;}方法二：創建哈希表
關于哈希表的知識點，推薦這篇文章：
https://blog.csdn.net/duan19920101/article/details/51579136?fromshare=blogdetail&sharetype=blogdetail&sharerId=51579136&sharerefer=PC&sharesource=2401_87935803&sharefrom=from_link
思路分析
利用哈希表，將所求差值放入哈希表中，直到找到兩個可以匹配成功的值
代碼實現
//方法二：利用哈希表public static int[] ToSum(int[] arr, int key){//創建哈希表Map<Integer, Integer> hashMap=new HashMap<>();//遍歷數組for(int i = 0; i < arr.length; i++){//計算當前元素與目標值的差值int complement=key-arr[i];//檢查哈希表中是否已存在這個差值作為鍵，如果存在，既找到了目標的兩個數if(hashMap.containsKey(complement)){return new int []{hashMap.get(complement),i};}//如果哈希表不存在這個差值，就將當前元素arr[i]及其索引存入哈希表hashMap.put(arr[i], i);}return new int [] {};}2.移動零
給定一個數組?nums，編寫一個函數將所有?0?移動到數組的末尾，同時保持非零元素的相對順序。
請注意?，必須在不復制數組的情況下原地對數組進行操作。
思路分析
代碼實現
//移動零public static void moveZeroes(int[] nums) {// 定義一個指針，用于指向當前非零元素應該放置的位置int nonZeroIndex = 0;// 遍歷數組for (int i = 0; i < nums.length; i++) {// 如果當前元素不為0if (nums[i] != 0) {// 將該非零元素放置到nonZeroIndex指向的位置nums[nonZeroIndex] = nums[i];// nonZeroIndex后移一位，為下一個非零元素做準備nonZeroIndex++;}}// 當遍歷完數組后，nonZeroIndex之后的位置都應該填充為0for (int i = nonZeroIndex; i < nums.length; i++) {nums[i] = 0;}}四.二分查找
原理：
搜索過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結束；
如果某一特定元素大于或小于中間元素，則在數組大于或小于中間元素的那一半中查找，而且此過程可以遞歸進行，直到找到要查找的元素，或者整個數組范圍被搜索完。
思路分析
1.首先確定該數組的中間的下標 mid=（left+right）/2
2.然后讓需要查找的數findVal和arr[mid]比較
2.1 findVal>arr[mid]，說明你要查找的數在mid的右邊，因此需要遞歸的向右查找
2.2 findVal<arr[mid]，說明你要查找的數在mid的左邊，因此需要遞歸的向左查找
2.3 findVal==arr[mid]說明找到，就返回索引下標
代碼實現
//二分查找public static int binarySearch(int[] arr, int left, int right, int findVal){// 當left >right時，說明遞歸整個數組, 沒有找到if(left>right){return -1;}int mid = (left + right)/2;int midVal = arr[mid];if(findVal<midVal){return binarySearch(arr, left, mid - 1, findVal);//向左遞歸} else if ( findVal>midVal) //向右遞歸{return binarySearch(arr, mid + 1, right, findVal);}else{return mid;//返回索引}}例題實踐
搜索插入位置
給定一個排序數組和一個目標值，在數組中找到目標值，并返回其索引。如果目標值不存在于數組中，返回它將會被按順序插入的位置。
請必須使用時間復雜度為?O(log n)?的算法。
思路分析
根據題目可知，本題要用二分查找法
代碼實現
//搜索插入位置public int searchInsert(int[] nums, int target) {int left=0;//初始化左邊界的第一個位置int right=nums.length-1;//初始化數組的最后一個位置//當左邊界小于右邊界時繼續循環while (left<=right){int mid=(left+right)/2;//找到中間值if(nums[mid]==target){return mid;//如果中間位置等于目標值，則返回} else if (nums[mid]>target) {right=mid-1;//中間值大于目標值，在左半部分查找}else{left=mid+1;//中間值小于目標值，則在右半部分}}return left;//返回左邊界為插入值}
