# LeetCode Easy 704. Binary Search

tags: leetcode

問題

• Explore
• Problems

整列された(降順に)$n$個の要素を持つ整数列numsとtargetという値を与えられたとき, numsにあるtargetを探す関数を書け.

もしtargetが存在するならそのインデックスを返し, そうでなければ-1を返せ

アイデア

真ん中の要素と比較して, targetとの大小によって左側か右側から探します

解法

• left, rightという変数で探索する配列の範囲を指定します
• 探索する配列の中央midを探索します
  • この要素がtargetと一致したらmidを返します
  • この要素がtargetより小さければ, 真ん中より後にtargetより大きい可能性のある数があるのでleftにmid+1を代入します
  • そうでなければ真ん中より前にあります
• 見つからなければ-1を返します

計算量

配列の要素数を$N$とします

• 時間計算量
  • 探索する範囲は半々になっていくので$2^{x} = N$であり, $x = \log n$
  • つまり, $O(\log n)$です
• 空間計算量
  • 新たに変数は定数個なので$O(1)$です

C++

class Solution {
public:
  int search(vector<int>& nums, int target){
    if(nums.size() == 0)
      return -1;

    int left = 0, right = nums.size() - 1;
    while(left <= right){
      int mid = left + (right - left) / 2;
      if(nums[mid] == target){ return mid; }
      else if(nums[mid] < target) { left = mid + 1; }
      else { right = mid - 1; }
    }
    
    return -1;
  }
};