# Binary Search

## 50. Pow(x, n) 求x的n次方

Implement pow(x, n), which calculates x raised to the power n (xn). Example 1: Input: 2.00000, 10 Output: 1024.00000 Example 2: Input: 2.10000, 3 Output: 9.26100 Example 3: Input: 2.00000, -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25 Note: -100.0 < x < 100.0 n is a 32-bit signed integer, within the range [−231, 231 − 1] 求x的n次方,利用递归这班计算 double myPow3(double x,int n){ if (n==0) return 1; double half = myPow3(x, n/2); if (n%2==0) return half*half; if (n>0) return half*half*x; return half*half/x; }

## 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 : Input: [1,3,5,6], 5 Output: 2 Example 2 : Input: [1,3,5,6], 2 Output: 1 Example 3 : Input: [1,3,5,6], 7 Output: 4 Example 4 :

## 34. Search for a Range 搜索一个范围

Given an array of integers 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]. For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4]. 解法1 这道题让我们在一个有序数组中查找与输入target相同的起始位置和结束位置,限定时间复杂度为O(logn),这个是典型的二分查找时间复杂度.这道题我们先采用二分法找到一个与target相同的index,再想index的左边和右边搜索. class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { int index = search(nums,0,nums.

## 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. Difficulty: Medium 这道题让我们求一个旋转有序数组中是否存在一个给定的值,存在返回下标,不存在返回-1.如体重的例子0 1 2 4 5 6 7,我们不知道从哪开始旋转的,他的选择情况有7种

## 29. Divide Two Integers 两数相除

Divide two integers without using multiplication, division and mod operator. If it is overflow, return MAX_INT. Difficulty: Medium 这道题让我们求两个数相除A/B,并且不让使用乘法,除法,取余运算.这样我们只能优先想到位运算和加减法了. 假设A>B,最容易想到的是把A-B赋值给A,并且结果+1,然后再把A-B赋值给A,结果+1.这样一直下去.不过如果是2147483647/1这种情况不会不会通过OJ,因为效率太低,会提示Time Limit Exceeded,不可行.回头想想上面的位运算还没用到,如果A>2*B那么结果是不是加2,如果A>2*2*2B结果是不是加2*2.定义t为除数,p为结果的计数m为被除数的绝对值,n为除数的绝对值.例如100/2 t (除数) p (计数) res (结果) m (被除数) t (除数) p (计数) res (结果) m (被除数) t (除数) p (计数) res (结果) m (被除数) 2 1 32 36 2 1 48 4 2 1 50 0 4 2 4 2 4 2 8 4 8 4 16 8 16 8 32 16 32 16 64 32 解法1 class Solution { public: int divide(int dividend, int divisor) { if (divisor==0||(dividend==INT_MIN&&divisor==-1)) return INT_MAX; int sign = ((dividend<0)^(divisor<0))?

## 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)). Example1: nums1 = [1, 3] nums2 = [2] The median is 2.0 Example2 nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5 分析 解法一: 思路来自Very concise O(log(min(M,N))) iterative solution with detailed explanation 看到O(log (m+n))一般来说就是分治法或是二分搜索,一个数组(长度为N)在中间切一刀,那它左边的索引L为(N-1)/2,右边的索引R为N/2.