🌞 題目：

🌏在有序數組A中，查找目標值target
🌏如果找到返回索引
🌏如果找不到返回-1

算法描述	解釋
前提	給定一個內含n個元素的有序數組A，滿足A0<=A1<=A2<=·······<=An-1,一個待查值target
1	設置left=0；right = n - 1
2	如果left > right ，結束查找，沒找到
3	設置mid = (left + right )/2，mid為中間索引
4	如果target < Am，設置right = mid -1，跳到第2步
5	如果target > Am，設置left = mid +1，跳到第2步
6	如果Am = target，結束查找，找到了

算法實現

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

注解：

1.為什么while循環條件是left<=right，而不是left<right？
因為當left=right時，mid=left=right可能為我們想要查找的值

2.為什么mid = (left+right)>>>1，而不是(left+right)/2呢？ >>>是無符號右移，無符號右移一位相當于除2取整。 不用(left+right)/2原因是，當left+right的值超過int類型的正整數最大范圍，其值就會由正變負

在其他的資料中二分查找與這個代碼不一樣，

?? 二分查找的改動版

public static int binarySearch1(int[] arr,int target) {int left=0;int right = arr.length;      //第一處改動while(left < right) {        //第二處改動int mid = (left+right)>>>1;if(target < arr[mid]) {right = mid;          //第三處改動}else if (arr[mid] < target) {left = mid + 1;}else {return mid;}}return -1;}

??注解：

right=arr.length，作為一個邊界存在，left可能為我們的查找目標，但是right一定不是我們要找到的目標

🚀圖解演示：

查找13

??在Java中其實已經提供了二分查找的方法binarySearch

public class Test {public static void main(String[] args) {int[] arr ={1,2,3,4,5,5,6};int target = Arrays.binarySearch(arr,3);System.out.println(target);}
}

🚠運行結果：

2

🚩二分查找對重復元素的處理

📍重復元素最靠右的元素

說明：查找元素為重復元素的話，會查找到最右邊的重復元素
Returns：
找到則返回最靠右索引
找不到返回-1

//重復元素最靠右的元素
public class Test5 {public static int binarySearch2(int[] arr,int target) {int left = 0;int right = arr.length-1;int cand = -1;while (left <= right) {int mid = (left + right)>>>1;if(target < arr[mid]) {right = mid-1;} else if (arr[mid] < target) {left = mid+1;}else {cand = mid;left = mid+1;}}return cand;}
}

說明：返回<=target的最右邊的索引
Returns：
找到則返回最靠右索引
找不到返回小于target最右邊的索引

 public static int binarySearchRightMost(int[] arr,int target){int left = 0;int right = arr.length-1;while(left <= right) {int mid = (left + right )>>>1;if(target < arr[mid]){right = mid-1;}else {left = mid + 1;}}return left-1;}

📍重復元素最靠左的元素

說明：查找元素為重復元素的話，會查找到最左邊的重復元素
Returns：
找到則返回最靠左索引
找不到返回-1

 public static int binarySearch2(int[] arr,int target) {int left = 0;int right = arr.length-1;int cand = -1;while (left <= right) {int mid = (left + right)>>>1;if(target < arr[mid]) {right = mid-1;} else if (arr[mid] < target) {left = mid+1;}else {cand = mid;right = mid - 1;}}return cand;}

說明：
返回>=target最左邊的索引
Returns：
找到則返回最靠左索引
找不到返回比target大的最左邊索引

 public static int binarySearchLeftMost(int[] arr,int target) {int left=0;int right = arr.length-1;while(left <= right) {int mid = (left + right)>>>1;if(target <= arr[mid]) {right = mid - 1;}else  {left = mid + 1;}}return left;}

圖解：

🚆leetcode二分查找題

1??1.給定一個 n 個元素有序的（升序）整型數組 nums 和一個目標值 target ，寫一個函數搜索 nums 中的 target，如果目標值存在返回下標，否則返回 -1。
? 鏈接: 二分查找

提示：
你可以假設 nums 中的所有元素是不重復的。
n 將在 [1, 10000]之間。
nums 的每個元素都將在 [-9999,9999]之間。

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

2??2.給定一個排序的整數數組 nums 和一個整數目標值 target ，請在數組中找到 target ，并返回其下標。如果目標值不存在于數組中，返回它將會被按順序插入的位置。
請必須使用時間復雜度為 O(log n) 的算法。
? 鏈接: 搜索插入位置

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

3??3.給你一個按照非遞減順序排列的整數數組 nums，和一個目標值 target。請你找出給定目標值在數組中的開始位置和結束位置。

如果數組中不存在目標值 target，返回 [-1, -1]。

你必須設計并實現時間復雜度為 O(log n) 的算法解決此問題。
? 鏈接: 在排序數組中查找元素的第一個和最后一個位置

class Solution {public int[] searchRange(int[] nums, int target) {int x=left(nums,target);if(x==-1){return new int[]{-1,-1};}else{return new int[]{x,right(nums,target)};}}public int left(int[] nums,int target) {int i=0;int j=nums.length-1;int cand=-1;while(i<=j){int  m=(i+j)>>>1;if(target<nums[m]){j=m-1;}else if(nums[m]<target){i=m+1;}else{cand=m;j=m-1;}}return cand;}public int right(int[] nums,int target) {int i=0;int j=nums.length-1;int cand=-1;while(i<=j){int  m=(i+j)>>>1;if(target<nums[m]){j=m-1;}else if(nums[m]<target){i=m+1;}else{cand=m;i=m+1;}}return cand;}
}