Leetcode二分查找算法算法

Python的二分搜索模块

#从左边开始找一个位置 bisect.bisect_left(arr, target) #从右边找到一个位置 bisect.bisect_right(arr, target) bisect.bisect(arr, target) #有序插入 bisect.insort(arr, target)#例：arr:[1，2，2，4，5，6] bisect_left(arr,2) => 1 bisect_right(arr, 2) => 3

Search for a Range
Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4]. If the target is not found in the array, return [-1, -1].

Python代码

import bisect class Solution: def searchRange(self, nums, target): re1 = bisect.bisect_left(nums,target) re2 = bisect.bisect(nums,target) if re2 == re1: return [-1,-1] return [re1, re2-1]

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.

#先找出旋转点 #通过realmid = (mid + rot) % n找出真实的中点 class Solution(object): def search(self, nums, target): lo, hi = 0, len(nums)-1 while lo < hi: mid = (lo + hi) // 2 if nums[mid] > nums[hi]: lo = mid + 1 else: hi = mid rot = lo lo, hi = 0, len(nums)-1 while lo <= hi: mid = (hi + hi) // 2 realmid = (mid + rot) % len(nums) if nums[realmid] == target: return realmid if nums[realmid] < target: lo = mid + 1 else: hi = mid - 1 return -1

public int search(int[] A, int target) { int lo = 0; int hi = A.length - 1; if (hi < 0) { return -1; } while (lo < hi) { int mid = (lo + hi) / 2; if (A[mid] == target) return mid; if (A[lo] <= A[mid]) { if (target >= A[lo] && target < A[mid]) { hi = mid - 1; } else { lo = mid + 1; } } else { if (target > A[mid] && target <= A[hi]) { lo = mid + 1; } else { hi = mid - 1; } } } return A[lo] == target ? lo : -1; }