---
# System prepended metadata

title: Untitled

---

Given a **sorted** (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.

```
Input: nums = [1, 2, 3, 4, 5, 6], target = 3
Output: 2
Input: nums = [2, 4, 5, 6, 11, 17], target = 10
Output: -1
```

```
public int binarySearch(int[] nums, int target) {
    if (nums == null || nums.length == 0) return -1;
    
    // 2, 4, 5, 6, 11, 17
    // 10
    int left = 0;
    int right = nums.length - 1; // 5
    while (left <= right) {
        int midIdx = (left + right) / 2;
        int mid = nums[midIdx];
        
        if (target == mid) {
            return midIdx;
        } else if (target > mid) {
           left = midIdx + 1; // 1 
        } else {
           right = midIdx - 1; //3
        }
    }
    
    return -1;
}
```

    Map<String, Map<Int, String>>



```
class Data {
    String val;
    int time;
    Data(String val, int time) {
        this.val = val;
        this.time = time;
    }
}
class TimeMap {
    Map<String, List<Data>> map;
    public TimeMap() {
        map = new HashMap<String, List<Data>>();
    }
    
    public void set(String key, String value, int timestamp) {
        if (!map.containsKey(key)) map.put(key, new ArrayList<Data>());
        map.get(key).add(new Data(value, timestamp));
    }
    
    public String get(String key, int timestamp) {
        if (!map.containsKey(key)) return "";
        return binarySearch(map.get(key), timestamp);
    }
    
    protected String binarySearch(List<Data> list, int time) {
        int low = 0, high = list.size() - 1;
        while (low < high) {
            int mid = (low + high) >>> 1;
            if (list.get(mid).time == time) return list.get(mid).val;
            if (list.get(mid).time < time) {
                if (list.get(mid+1).time > time) return list.get(mid).val;
                low = mid + 1;
            }
            else high = mid -1;
        }
        return list.get(low).time <= time ? list.get(low).val : "";
    }
}

```

```
class CarouselQueue<T> {

    private val list: MutableList<T> = mutableListOf()

    private var nextIndex = 0

    fun addAll(elements: Collection<T>) {
      list.addAll(elements)
    }

    fun isEmpty() = list.isEmpty()

    fun next(): T {
        val next = list[nextIndex]
        nextIndex ++
        nextIndex %= list.size
        return next
    }
}
```