LeetCoding Challenge Oct. 8: Binary Search

LeetCode October Challenge の 8 日目。

今日の問題は Binary Search。

問題の概要

• 二分探索を実装する
  • 要素が見つかったらそのインデックスを、なかったら -1 を返す

考え方

• 一昨日, 昨日 に引き続き (略)
• ただの二分探索と侮ることなかれ、バグなく実装するのは意外と難しいですよね…
  • 特に問題になりやすいのが、区間中央のインデックスを求める処理で、オーバーフローしないようにしなければならない (今回の問題だと要素の数は最大で 10,000 なので、オーバーフローを気にしなくてもいいが…)
    • Java だと論理右ビットシフト演算子 >>> があるので、これを使えばオーバーフローは怖くない！
  • あとは区間の右端が include なのか exclude なのかを意識すればよさそう
• 以下のコードで submit して runtime 0ms 達成 👍

コード

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

            if (nums[mid] < target) {
                left = mid + 1;
            } else {  // nums[mid] > target
                right = mid - 1;
            }
        }
        return -1;
    }
}