704. Binary Search

مسئله: جستجوی دودویی (Binary Search) در آرایه مرتب

فرض کنید آرایه‌ای از اعداد صحیح به نام nums دارید که به ترتیب صعودی مرتب شده است و همچنین یک عدد صحیح target به شما داده شده است. تابعی بنویسید که target را در nums جستجو کند. اگر target وجود داشته باشد، مکان یا index آن را برگردانید. در غیر این صورت، 1- را برگردانید.

الگوریتم باید دارای پیچیدگی زمانی O(log n) باشد.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

محدودیت‌ها:

1 <= nums.length <= 10^4
-10^4 < nums[i], target < 10^4
All the integers in nums are unique.
nums is sorted in ascending order.

راه‌حل ۱: جستجوی دودویی

مرز چپ جستجوی دودویی را با left = 0 و مرز راست را با right = n-1 تعریف می‌کنیم (که در آن n طول آرایه است).

در هر تکرار، موقعیت میانی mid = (left + right) / 2 را محاسبه می‌کنیم و سپس اندازه nums[mid] و target را مقایسه می‌کنیم:

• اگر nums[mid] ≥ target، به این معنی است که target در بازه [left, mid] قرار دارد، بنابراین right را به mid به‌روز می‌کنیم.
• در غیر این صورت، target در بازه [mid+1, right] قرار دارد، بنابراین left را به mid+1 به‌روز می‌کنیم.

زمانی که left ≥ right شد، بررسی می‌کنیم که آیا nums[left] با target برابر است یا خیر. اگر برابر بود، left را برمی‌گردانیم، در غیر این صورت -1 را برمی‌گردانیم.

پیچیدگی زمانی این الگوریتم O(log⁡ n) است، که در آن n طول آرایه nums می‌باشد. پیچیدگی فضایی نیز O(1) است.

func search(nums []int, target int) int {
 left, right := 0, len(nums)-1
 for left < right {
  mid := (left + right) >> 1
  if nums[mid] >= target {
   right = mid
  } else {
   left = mid + 1
  }
 }
 if nums[left] == target {
  return left
 }
 return -1
}