[LeetCode] 702. Search in a Sorted Array of Unknow

zlyBear 發(fā)布于2019-08-16 14:00 / 1783人閱讀

Problem

Given an integer array sorted in ascending order, write a function to search target in nums. If target exists, then return its index, otherwise return -1. However, the array size is unknown to you. You may only access the array using an ArrayReader interface, where ArrayReader.get(k) returns the element of the array at index k (0-indexed).

You may assume all integers in the array are less than 10000, and if you access the array out of bounds, ArrayReader.get will return 2147483647.

Example 1:

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

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

Note:

You may assume that all elements in the array are unique.
The value of each element in the array will be in the range [-9999, 9999].

Solution

class Solution {
    public int search(ArrayReader reader, int target) {
        //find higher bound
        int r = 1;
        while (reader.get(r) < target) r *= 2;
        //then you know lower bound
        int l = r/2;
        while (l <= r) {
            int m = l+(r-l)/2;
            if (reader.get(m) == target) return m;
            else if (reader.get(m) < target) l = m+1;
            else r = m-1;
        }
        return -1;
    }
}

云服務(wù)器 GPU云服務(wù)器 sorted-array array_search函數(shù) in_array() in_array

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/72702.html

相關(guān)文章

前端 | 每天一個(gè) LeetCode

摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...

張漢慶 2019-08-23 13:42 評(píng)論0 收藏0
leetcode 部分解答索引（持續(xù)更新～）

摘要：前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖恪Ｋ栽谶@里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個(gè)索引嘻嘻。順序整理 1~50 1...

leo108 2019-08-15 14:26 評(píng)論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡(jiǎn)單難度攻略已經(jīng)到題，所以后面會(huì)調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區(qū)別...

tain335 2019-08-26 10:28 評(píng)論0 收藏0
[Leetcode] Search in Rotated Sorted Array 搜索旋轉(zhuǎn)有序數(shù)組

摘要：如果左邊的點(diǎn)比右邊的大，說明這兩個(gè)點(diǎn)之間有一個(gè)旋轉(zhuǎn)點(diǎn)，導(dǎo)致了不再有序。因?yàn)橹挥幸粋€(gè)旋轉(zhuǎn)點(diǎn)，所以一分為二后，肯定有一半是有序的。 Search in Rotated Sorted Array I Suppose a sorted array is rotated at some pivot unknown to you beforehand.(i.e., 0 1 2 4 5 6 7 mi...

thursday 2019-08-14 12:38 評(píng)論0 收藏0
[LeetCode] Convert Sorted Array to Binary Search T

摘要：思路根據(jù)的性質(zhì)，問題轉(zhuǎn)化為找一個(gè)里的中位數(shù)，用一個(gè)函數(shù)，一路找中點(diǎn)，再通過前序遍歷的方法把起來代碼 Convert Sorted Array to Binary Search Tree With Minimal Height Given a sorted (increasing order) array, Convert it to create a binarytree with m...

willin 2019-08-16 10:33 評(píng)論0 收藏0