二分查找

162. Find Peak Element题目A peak element is an element that is strictly greater than its neighbors. Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks. You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array. You must write an algorithm that runs in O(log n) time. Example...

35. Search Insert Position题目Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Example 1: 12Input: [1,3,5,6], 5Output: 2 Example 2: 12Input: [1,3,5,6], 2Output: 1 Example 3: 12Input: [1,3,5,6], 7Output: 4 Example 4: 12Input: [1,3,5,6], 0Output:...

69. Sqrt(x)Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well. You must not use any built-in exponent function or operator. For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python. Example 1: 123Input: x = 4Output: 2Explanation: The square root of 4 is 2, so we return 2. Example 2: 123Input: x = 8Output: 2Explanation: The square root of 8 is 2.82842..., and since we round it down to...

34. Find First and Last Position of Element in Sorted Array题目Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. Your algorithm's runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. Example 1: Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4] Example 2: Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1] 查找第一个出现的位置： 当找到目标值时，不立即返回，而是继续向左查找（right...

33. Search in Rotated Sorted Array题目Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. Your algorithm's runtime complexity must be in the order of O(log n). Example 1: Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 Example 2: Input: nums...

4. Median of Two Sorted Arrays题目There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). You may assume nums1 and nums2 cannot be both empty. Example 1: nums1 = [1, 3] nums2 = [2] The median is 2.0 Example 2: nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5 题目大意给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m +...

5. Longest Palindromic Substring题目Given a string s, return the longest palindromic substring in s. Example 1: 1234Input: s = "babad"Output: "bab"Note: "aba" is also a valid answer. Example 2: 123Input: s = "cbbd"Output: "bb" Example 3: 123Input: s = "a"Output: "a" Example 4: 123Input: s = "ac"Output: "a" Constraints: 1 <= s.length <= 1000 s consist of only digits and English letters...