題目描述
給定一個 n 個元素有序的（升序）整型陣列 nums 和一個目標值 target ，寫一個函式搜索 nums 中的 target，如果目標值存在回傳下標，否則回傳 -1，
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/binary-search
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
簡要描述二分法
首先應為一個有序數列，我們將會數字設定為一個陣列nums，將要在陣列中尋找的目標設定為target，在陣列中，對陣列中間值nums[middle]與target進行判斷，并對其進行空間的壓縮，然后再次判斷新的nums[middle]與target的大小關系，直到nums[middle]與target相等為止
思路
- 首先明確題目要求，為尋找目標值，若存在回傳下標，不存在則回傳-1，標準的二分查找
- 明確了二分查找要求后，確定使用左閉右倍訓是左閉合又開，即選擇[left,right]還是[left,right)，這里我選擇的是左閉右閉
- 確定了使用左閉右閉寫法之后，便應該明確怎么寫代碼，由于目標值在[left,right]區間，所以while(left ? right)中？處應填寫<= ,因為在[left,right]區間中,left == right是存在的，例[1,1]，所以應當使用<=
- 同時判斷陳述句if (nums[middle] > target) 時,由于middle大于目標值，所以即目標值出現在左半邊，所以應當將right(即右邊界)賦值為middle - 1，因為判斷條件為if (nums[middle] > target)，此時的nums[middle] 必然不是目標值，所以可以自然往左一位
- 而判斷陳述句if (nums[middle] < target)時，由于middle小于目標值，所以即目標值出現在右半邊，所以應當將left(即左邊界)賦值為middle + 1，原因參考上一點
- 當nums[middle] = tarage 時，直接return middle輸出結果即可
- 最后在while回圈外寫入return -1表示目標值不存在即可
代碼
class Solution {
public int search(int[] nums, int target) {
int left = 0 ;
int right = nums.length -1;
while(left <= right){
int middle = left + (right - left) / 2;
if(nums[middle] > target)
right = middle -1;
else if(nums[middle] < target)
left = middle + 1;
else if(nums[middle] == target)
return middle;
}
return -1;
}
}
提交截圖
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/542848.html
標籤：Java