LeetCode每日十题---二分查找

1.题目描述

2.笔者分析

先对二分查找做个总结吧，两指针起始位置分别为数组的最小下标和最大下标；比较中间下标对应的值与目标值的大小。若小于目标值，则左指针下标增加到M+1(假设数组递增排序)，若大于目标值，则右指针下标递减到M-1；跳出循环的条件为找到目标值或左指针下标大于右指针下标。但二分查找的题一定要学会变通，并非都是这种格式。该题代码如下：

int left=0; int right=array.length-1; int mid; while(left<=right) { mid=left+(right-left)/2;//防止left+right溢出 if(array[mid]>target) right=mid-1; else if(array[mid]<target) left=mid+1; else return mid; } return -1;//没找到

2题目描述

2.1笔者分析

因为空格比较多，所以开始肯定是去除空格，想到的是用HashMap，然后将非空格的字符串存入一个数组，用二分法。之后再回原数组匹配，有点麻烦。看了评论区做了一些优化，就是用稀疏数组存字符串的同时也保存其在原数组内的下标，代码如下。

class Solution { public int findString(String[] words, String s) { String[][] arrays=new String[words.length][2]; int count=0; for(int x=0;x<words.length;x++){ if(!words[x].equals("")){ arrays[count][0]=words[x]; arrays[count][1]=String.valueOf(x); count++; } } for(int x=0;x<count;x++){ if(arrays[x][0].equals(s)){ return Integer.parseInt(arrays[x][1]); } } return -1; } }

总结

二分法给人一种万金油的感觉，太暴力了效率还高。每日打卡二十九天，以下图为证