二分查找

1. 原始查找一个数

 1 /*
 2 * https://leetcode-cn.com/problems/binary-search/
 3 *
 4 * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，
 5 * 如果目标值存在返回下标，否则返回 -1。
 6 */
 7 public class code070_binarySearch
 8 {
 9     public int search(int[] nums, int target) {
10         int start = 0, end = nums.length - 1;
11         while(start <= end){
12             int mid = start + (end - start) / 2;
13             if(nums[mid] == target){
14                 return mid;
15             }else if(nums[mid] < target){
16                 start = mid + 1;
17             }else if(nums[mid] > target){
18                 end = mid - 1;
19             }
20         }
21         return -1;
22     }
23 }

2. 寻找左侧和右侧边界

 1 package leetcode_2020;
 2 /*
 3 * https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
 4 *
 5 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 6 *
 7 * 你的算法时间复杂度必须是 O(log n) 级别。
 8 *
 9 * 如果数组中不存在目标值，返回 [-1, -1]
10 */
11 public class code034_firstAndLastBybinarySearch
12 {
13     public int[] searchRange(int[] nums, int target) {
14         int rs[] = {-1, -1};
15         if (nums.length == 0)
16             return rs;
17 
18         //left
19         int start = 0, end = nums.length - 1;
20         while (start <= end){
21             int mid = start + (end - start) / 2;
22             if (nums[mid] == target)
23                 end = mid - 1;
24             else if (nums[mid] < target)
25                 start = mid + 1;
26             else if(nums[mid] > target)
27                 end = mid - 1;
28         }
29         if(start >= nums.length || nums[start] != target)
30             rs[0] = -1;
31         else
32             rs[0] = start;
33 
34         //right
35         start = 0; end = nums.length - 1;
36         while (start <= end){
37             int mid = start + (end - start) / 2;
38             if (nums[mid] == target)
39                 start = mid + 1;
40             else if (nums[mid] < target)
41                 start = mid + 1;
42             else if(nums[mid] > target)
43                 end = mid - 1;
44         }
45         if(end < 0 || nums[end] != target)
46             rs[1] = -1;
47         else
48             rs[1] = end;
49         return rs;
50     }
51 }

注意：

　　统一：

　　end = num.length - 1

　　while: <=

　　mid = start + (end - start) / 2

　　mid + 1 / mid - 1