704.二分查找
题目链接 : https://leetcode.cn/problems/binary-search/description/
思路:切记二分查找要基于排序好的数组或者数据,否则二分查找必不能使用!!!!!!!!!
双指针写最简单,一个头指针从0开始,一个尾指针从数组长度-1开始,中间指针是头+尾/2,每次比较头尾中间指针的值是否是target,如果是就返回中间值的下标(也就是中间指针),如果中间值小于target就把头指针移到中间指针右边;如果中间值大于target就把尾指针移到中间指针左边.如果头指针大于尾指针那么跳出循环.
之后如果像这样简单题的思路我就不会写出来了,太浪费时间了....
这题里面这句话值得一品
int mid = left + (right - left) >> 1;
这里用了位运算
顺便贴一张运算符优先级的图
代码如下:
点击查看代码
@Test
public void test1(){
int[] nums = {-1,0,3,5,9,12};
System.out.println(search(nums, 9));
}
public int search(int[] nums, int target) {
if (target < nums[0] || target > nums[nums.length - 1]) {
return -1;
}
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) >> 1;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
27. 移除元素
题目链接:https://leetcode.cn/problems/remove-element/description/
这题太简单了,不写思路了
点击查看代码
public int removeElement(int[] nums, int val) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != val) {
nums[count] = nums[i];
count++;
}
}
return count;
}