704.Classical_Binary_Search.md

704. Binary Search

https://leetcode-cn.com/problems/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], 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

Constraints:

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

相关企业

亚马逊 Amazon|8
谷歌 Google|5
苹果 Apple|5
Facebook|4
微软 Microsoft|4
SAP 思爱普|3
百度|2
优步 Uber|2
彭博 Bloomberg|2

相关标签

• Array
• Binary Search

相似题目

• Search in a Sorted Array of Unknown Size 中等

三个思路：

思路	时间复杂度	问题
遍历	O(N)	太慢
HashTable	O(1)	是在内存上操作，当数据集较大时，无法全放到内存上，那么就不能用了。
二分查找	O(logN)	磁盘上操作

my solution O(logn) - recursion

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0){
            return -1;
        }
        return this._search(nums, 0, nums.length-1, target);
    }

    private int _search(int[] nums, int left, int right, int target){
        if (right - left <= 1){
            if (nums[left] == target){
                return left;
            }else if (nums[right] == target){
                return right;
            }else {
                return -1;
            }
        }

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

Binary Search

// version 1: with  template
public class Solution {
    /**
     * @param A an integer array sorted in ascending order
     * @param target an integer
     * @return an integer
     */
    public int findPosition(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        int start = 0, end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        
        if (nums[start] == target) {
            return start;
        }
        if (nums[end] == target) {
            return end;
        }
        return -1;
    }
}

// version 2: without  template
public class Solution {
    /**
     * @param A an integer array sorted in ascending order
     * @param target an integer
     * @return an integer
     */
    public int findPosition(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        int start = 0, end = nums.length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        
        if (nums[start] == target) {
            return start;
        }
        return -1;
    }
}

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1

        start, end = 0, len(nums)-1
        while start + 1 < end:
            mid = start + (end - start) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                end = mid
            else:
                start = mid
        
        if nums[start] == target:
            return start
        if nums[end] == target:
            return end
        return -1