Skip to content

704-binary-search.md

Latest commit

聽

History

History
239 lines (173 loc) 路 4.72 KB

704-binary-search.md

File metadata and controls

239 lines (173 loc) 路 4.72 KB
Raw

Original link: leetcoder.net - LeetCoder: Fucking Good LeetCode Solutions

704. Binary Search - LeetCoder: Fucking Good LeetCode Solutions

LeetCode link: 704. Binary Search, difficulty: Easy.

LeetCode description of "704. Binary Search"

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

[Example 1]

Input: nums = [-1,0,3,5,9,12],>

Output: 4

Explanation: 9 exists in nums and its index is 4

[Example 2]

Input: nums = [-1,0,3,5,9,12],>

Output: -1

Explanation: 2 does not exist in nums so return -1

[Constraints]

  • 1 <= nums.length <= 10000
  • 104 < nums[i], target < 10000
  • All the integers in nums are unique.
  • nums is sorted in ascending order.

Intuition

Because it is an already sorted array, by using the middle value for comparison, half of the numbers can be eliminated each time.

Steps

The fastest and easiest way is to use the three indices left, right, and middle. If nums[middle] > target, then right = middle - 1, otherwise, left = middle + 1.

Complexity

  • Time complexity: O(log N).
  • Space complexity: O(1).

Java

class Solution {
    public int search(int[] nums, int target) {
        var left = 0;
        var right = nums.length - 1;

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

        return -1;
    }
}

Python

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            middle = (left + right) // 2

            if nums[middle] == target:
                return middle

            if nums[middle] > target:
                right = middle - 1
            else:
                left = middle + 1

        return -1

C++

class Solution {
public:
    int search(vector<int>& nums, int target) {
        auto left = 0;
        int right = nums.size() - 1; // Should not use 'auto' here because 'auto' will make this variable become `unsigned long` which has no `-1`.

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

        return -1;
    }
};

JavaScript

var search = function (nums, target) {
  let left = 0
  let right = nums.length - 1

  while (left <= right) {
    const middle = Math.floor((left + right) / 2)

    if (nums[middle] == target) {
      return middle
    }

    if (nums[middle] > target) {
      right = middle - 1
    } else {
      left = middle + 1
    }
  }

  return -1
};

C#

public class Solution
{
    public int Search(int[] nums, int target)
    {
        int left = 0;
        int right = nums.Length - 1;

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

        return -1;
    }
}

Go

func search(nums []int, target int) int {
    left := 0
    right := len(nums) - 1

    for left <= right {
        middle := (left + right) / 2

        if nums[middle] == target {
            return middle
        }

        if nums[middle] > target {
            right = middle - 1
        } else {
            left = middle + 1
        }
    }

    return -1
}

Ruby

def search(nums, target)
  left = 0
  right = nums.size - 1

  while left <= right
    middle = (left + right) / 2

    return middle if nums[middle] == target

    if nums[middle] > target
      right = middle - 1
    else
      left = middle + 1
    end
  end

  -1
end

Other languages

// Welcome to create a PR to complete the code of this language, thanks!