一、基本查找

递增数组，从头往尾查找，O(n)的时间即可找到

public static int find(int[] nums,int target){for(int i = 0;i<nums.length;i++){if(nums[i] == target){return nums[i];}}return -1;
}

二、二分查找与分治

有序的数组从头到尾找效率未免太低，就像给一本电话簿查找指定电话肯定不会从第一页开始翻

二分查找是一种高效的查找算法，通常用于在有序数组或列表中查找特定元素的位置。它的基本思想是将待查找区间不断缩小为两部分，然后比较中间元素与目标元素的大小，从而决定继续查找的方向。如果中间元素等于目标元素，则找到了；如果中间元素大于目标元素，则在左半部分继续查找；如果中间元素小于目标元素，则在右半部分继续查找。通过每次排除一半的元素，二分查找的时间复杂度为 O(log n)。

分治是一种算法设计策略，它将问题分解为多个子问题，然后递归地解决这些子问题，最后将子问题的解组合起来得到原问题的解。分治通常包括三个步骤：分解、解决和合并。在分解阶段，原问题被划分为一系列子问题；在解决阶段，对每个子问题进行递归求解；在合并阶段，将子问题的解合并成原问题的解。分治的经典应用包括归并排序和快速排序等。

在某些情况下，二分查找和分治可以结合使用。例如，在分治算法中，当问题的规模缩小到一定程度时，可以使用二分查找来解决子问题。这种结合能够充分利用二分查找的高效性质，并且在解决复杂问题时保持分治的思想。

1.循环的方式

需要注意的细节有循环继续条件是小于等于，有可能数组长度为1就一个元素并且满足目标

还有就是left + right可能超过大小，改除法为位运算会快很多

class Solution {public int search(int[] nums, int target) {int left = 0;int right = nums.length - 1;while(left <= right){int mid = left + ((right - left) >> 1);if(nums[mid] == target){return mid;}else if(nums[mid]>target){right = mid - 1;}else{left = mid + 1;}}return -1;}}

2.递归的方式

class Solution {public int search(int[] nums, int target) {return trace(nums,0,nums.length -1 ,target);}public int trace(int[] nums,int left,int right,int target){if(left <= right){int mid = left + ((right - left) >> 1);if(nums[mid] == target){return mid;}else if(nums[mid]>target){return trace(nums,left,mid-1,target);}else{return trace(nums,mid + 1,right,target);}}return -1;}}

3.元素中有重复的二分查找

如果是非递减的有重复元素的数组，找到最左侧的第一个

private static int binSearch(int[] nums, int target, int left, int right){if(left <= right){int mid = left + ((right - left)>>1);if(nums[mid] == target){while(nums[mid] == target){mid--;}return mid + 1;}else if(nums[mid] < target){binSearch(nums,target,mid + 1,right);}else {binSearch(nums,target,left,mid -1);}}return -1;}

当重复的元素很多的时候也可以采用二分法

private static int binSearch(int[] nums, int target, int left, int right){if(left <= right){int mid = left + ((right - left)>>1);if (nums[left] == target){return left;}if(nums[mid] == target){return binSearch(nums,target,left,mid);}else if(nums[mid] < target){return binSearch(nums,target,mid + 1,right);}else {return binSearch(nums,target,left,mid -1);}}return -1;}

递归三部曲：

第一步：确定参数和返回值

第二步：确定终止条件

当left>right时说明不符合条件终止

当nums[left]=target说明找到目标返回left ，left代表范围内的最左端

if (nums[left] == target){return left;
}

第三步：确定单层逻辑

二分查找逻辑，左闭右闭

相等的时候让最右端的right指向mid，二分向左缩小每次只移动右指针

只有nums[mid]小于target才移动left，这样就能保证left一定是范围内的最左端

if(nums[mid] == target){return binSearch(nums,target,left,mid);
}